【DFS+思维】codeforces 1092 F. Tree with Maximum Cost

F. Tree with Maximum Cost

time limit per test

2 seconds

memory limit per test

256 megabytes

You are given a tree consisting exactly of nn vertices. Tree is a connected undirected graph with n−1n−1 edges. Each vertex vv of this tree has a value avav assigned to it.

Let dist(x,y)dist(x,y) be the distance between the vertices xx and yy. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be vv. Then the cost of the tree is ∑i=1ndist(i,v)⋅ai∑i=1ndist(i,v)⋅ai.

Your task is to calculate the maximum possible cost of the tree if you can choose vv arbitrarily.

Input

The first line contains one integer nn, the number of vertices in the tree (1≤n≤2⋅1051≤n≤2⋅105).

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅1051≤ai≤2⋅105), where aiai is the value of the vertex ii.

Each of the next n−1n−1 lines describes an edge of the tree. Edge ii is denoted by two integers uiui and vivi, the labels of vertices it connects (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi).

It is guaranteed that the given edges form a tree.

Output

Print one integer — the maximum possible cost of the tree if you can choose any vertex as vv.

Examples

input

Copy

8
9 4 1 7 10 1 6 5
1 2
2 3
1 4
1 5
5 6
5 7
5 8

output

Copy

input

Copy

1
1337

output

Copy

Note

Picture corresponding to the first example: 【DFS+思维】codeforces 1092 F. Tree with Maximum Cost

You can choose the vertex 33 as a root, then the answer will be 2⋅9+1⋅4+0⋅1+3⋅7+3⋅10+4⋅1+4⋅6+4⋅5=18+4+0+21+30+4+24+20=1212⋅9+1⋅4+0⋅1+3⋅7+3⋅10+4⋅1+4⋅6+4⋅5=18+4+0+21+30+4+24+20=121.

In the second example tree consists only of one vertex so the answer is always 0.

题意：给你n个点n-1条边的无向图

为每一个节点确定一个权值

选择一个节点为根，提起整棵树，每个节点与根的距离*权值是它对答案的贡献

问你最大答案是多少

题解：

其实以此时的根节点的子节点为根，实际上只是把原来的值减去提起来的子节点的子树的权值再加上其他的权值

先dfs一次处理出每个节点的父亲，深度，以此节点为父节点的子树的权值

在dfs一遍处理出每个节点为根时的答案

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
ll a[maxn];
ll sum[maxn];
ll ans=0;
ll all[maxn];
int dep[maxn],fa[maxn];
vector <int> G[maxn];

void dfs(int x,int y,int deep)
{
    fa[x]=y;
    dep[x]=deep;
    sum[x]+=a[x];
    all[1]+=dep[x]*a[x];
    for(auto v:G[x])
    {
        if(v==y) continue;
        dfs(v,x,deep+1);
        sum[x]+=sum[v];
    }
}

void dfs2(int x,int fa)
{
    for(auto v:G[x])
    {
        if(v==fa) continue;
        all[v]=all[x]-sum[v]+(sum[1]-sum[v]);
        dfs2(v,x);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,all[i]);
    }
    cout<<ans<<endl;

    return 0;
}

【DFS+思维】codeforces 1092 F. Tree with Maximum Cost

F. Tree with Maximum Cost

相关推荐