FullDepthMorningShow

All boring tree-shaped lands are alike, while all exciting tree-shaped lands are exciting in their own special ways. What makes Treeland more exciting than the other tree-shaped lands are the raddest radio hosts in the local area: Root and Leaf. Every morning on FM 32.33 (repeating of course), Root and Leaf of The Full Depth Morning Show serve up the hottest celebrity gossip and traffic updates.

The region of Treeland is made of n cities, connected by n - 1 roads such that between every pair of cities there is exactly one simple path. The i-th road connects cities $u_i$ and $v_i$ , and has a toll of $w_i$ .

To reward their loyal listeners, The Full Depth Morning Show is giving away a number of travel packages! Root and Leaf will choose n - 1 lucky residents from the city that sends them the most fan mail. Each of those residents then gets a distinct ticket to a different city in Treeland.

Each city in Treeland has its own tax on prizes: $t_i$ . Let $d_{u, v}$ be the sum of the tolls on each road on the only simple path from city u to v. For a trip from city u to city v, the cost of that trip is then $(t_u + t_v) d_{u, v}$ .

The map of Treeland corresponding to the first sample input.

The shock jocks haven't quite thought through how much their prize is worth. They need to prepare a report to the radio executives, to summarize the expected costs. For each city that could win the prize, what is the total cost of purchasing all the tickets?

The first line of input is a single integer n ( $1 \leq n \leq 100\,000$ ). The next line has n space-separated integers $t_i$ ( $1\leq t_i \leq 1\,000$ ), the tax in each city. The following n - 1 lines each have 3 integers, $u_i, v_i, w_i$ , meaning the i-th road connects cities $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n$ ), with a toll of $w_i$ ( $1 \leq w_i \leq 1\,000$ ).

#include<bits/stdc++.h> using namespace std; typedef long long ll; unordered_map<int,unordered_map<int,int> >mp; vector<int> v[100500]; int i,n,m,x,y,z; ll res[100500],a[100500],b[100500],c[100500],s,a0[100500]; void dfs1(int x,int fa){ for(int i:v[x]){ if(i!=fa){ dfs1(i,x); if(x!=1){a[x]+=a[i];} b[x]+=b[i]; res[1]+=a[i]*mp[i][x]; c[1]+=b[i]*mp[i][x]; } } } void dfs2(int x,int fa){ if(x!=1){ res[x]=res[fa]+(s-2*a[x])*mp[fa][x]; c[x]=c[fa]+(n-2*b[x])*mp[fa][x]; } for(int i:v[x]){ if(i!=fa){dfs2(i,x);} } } int main(){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%lld",&a0[i]); a[i]=a0[i]; s+=a[i]; b[i]=1; } for(i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); mp[x][y]=mp[y][x]=z; v[y].push_back(x); v[x].push_back(y); } dfs1(1,0);dfs2(1,0); for(i=1;i<=n;i++){printf("%lld\n",res[i]+c[i]*a0[i]);} }

详情