F. Tree with Maximum Cost

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.

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.

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

Picture corresponding to the first example:

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 00.

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #define FOR(x, maxx) for(x = 1; x <= maxx; x++)

 #define ZERO(aa, x) memset(aa, x, sizeof(aa))

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = 2e5+;

 struct EDGE

 {

     int v, nxt;

 }edge[MAXN<<];

 int head[MAXN];

 LL sum[MAXN], sumk[MAXN];

 int cost[MAXN], dep[MAXN];

 int N, cnt;

 LL ans, res;

 void add(int from, int to)

 {

     edge[cnt].v = to;

     edge[cnt].nxt = head[from];

     head[from] = cnt++;

 }

 void init()

 {

     memset(head, -, sizeof(head));

     cnt = ;

     ans = ;

 }

 void dfs1(int now, int dh, int fa)

 {

     //puts("zjy");ans = max(res, ans);

     int to;

     sum[now] = cost[now];

     res += 1LL*cost[now]*dh;

 //    dep[now] = dh;

 //    f[now] = fa;

     //printf("now: %d\n", now);

     for(int i = head[now]; i != -; i = edge[i].nxt){

         to = edge[i].v;

         if(to != fa){

             dfs1(to, dh+, now);

             sum[now]+=sum[to];

         }

     }

 }

 void dfs2(int now, int fa)

 {

     ans = max(res, ans);

     int to;

     LL a, b, c;

     for(int i = head[now]; i != -; i = edge[i].nxt){

         to = edge[i].v;

         if(to == fa) continue;

         a = sum[now], b = sum[to], c = res;

         res-=sum[to];               //当前子树的节点距离-1

         res+=sum[now]-sum[to];      //当前非子树节点距离+1

         sum[now]-=sum[to];

         sum[to] = a;

         dfs2(to, now);

         sum[now] = a;   //还原

         sum[to] = b;

         res = c;

     }

 }

 int main()

 {

     int i, j;

     init();

     scanf("%I64d", &N);

     FOR(i, N) scanf("%I64d", &cost[i]);

     int u, v;

     for(i = ; i < N; i++){

         scanf("%d %d", &u, &v);

         add(u, v);

         add(v, u);

     }

     //puts("zjy");

     dfs1(, , );      //第一次递归求初始值

     dfs2(, );

     printf("%I64d\n", ans);

     return ;

 }

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #define FOR(x, maxx) for(x = 1; x <= maxx; x++)

 #define ZERO(aa, x) memset(aa, x, sizeof(aa))

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = 2e5+;

 struct EDGE

 {

     int v, nxt;

 }edge[MAXN<<];

 int head[MAXN], cnt;;

 LL sum[MAXN], dp[MAXN];

 LL cost[MAXN];

 LL ans, res;

 LL SSum;

 int N;

 void add(int from, int to)

 {

     edge[cnt].v = to;

     edge[cnt].nxt = head[from];

     head[from] = cnt++;

 }

 void init()

 {

     memset(head, -, sizeof(head));

     memset(dp, , sizeof(dp));

     SSum = 0LL;

     cnt = ;

     ans = ;

 }

 void dfs(int now, int fa)

 {

     int to;

     sum[now] = cost[now];

     for(int i = head[now]; i != -; i = edge[i].nxt){

         to = edge[i].v;

         if(to == fa) continue;

         dfs(to, now);

         sum[now]+=sum[to];

         dp[now] = dp[now] + dp[to] + sum[to];

     }

 }

 void solve(int now, int fa)

 {

     int to;

     if(fa) dp[now] = dp[fa]+SSum-*sum[now];

     for(int i = head[now]; i != -; i = edge[i].nxt){

         to = edge[i].v;

         if(to == fa) continue;

         solve(to, now);

     }

     ans = max(ans, dp[now]);

 }

 int main()

 {

     init();

     scanf("%d", &N);

     for(int i = ; i <= N; i++){

         scanf("%I64d", &cost[i]);

         SSum+=cost[i];

     }

     int u, v;

     for(int i = ; i < N; i++){

         scanf("%d %d", &u, &v);

         add(u, v);

         add(v, u);

     }

     //puts("zjy");

     dfs(, );      //第一次递归求初始值

     solve(, );

     printf("%I64d\n", ans);

     return ;

 }