[UPC] Radio Prize | 换根dp

[UPC] Radio Prize | 换根dp

目录

​​题目描述​​​​输入​​​​输出​​​​样例输入​​​​样例输出​​​​参考​​

题目描述

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 ui and vi , and has a toll of wi.

To reward their loyal listeners, The Full Depth Morning Show is giving away a number of travel packages! Root and Leaf will choose n 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.

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 ≤ n ≤ 100 000). The next line has n space-separated integers ti (1 ≤ ti ≤ 1 000), the tax in each city. The following n-1 lines each have 3 integers, ui, vi, wi, meaning the i-th road connects cities ui and vi (1 ≤ ui, vi ≤ n), with a toll of wi (1 ≤ wi ≤ 1 000).

输出

Output n lines. On the i-th line, output a single integer: the cost of purchasing tickets if city i wins the contest.

样例输入

【样例1】

52 5 3 4 11 2 22 4 54 3 35 2 6

【样例2】

64 3 3 4 3 31 3 22 1 11 4 64 5 66 4 2

样例输出

【样例1】

130159191163171

【样例2】

209206232209336232

const int maxn = 1e6+7;struct node { int v,w,nex;} e[maxn];bool vis[maxn];ll dis[maxn],disval[maxn],a[maxn];ll sumNode[maxn],sumVal[maxn];ll totval;int head[maxn];int cnt = 0;int n,m;typedef pair PII;void init() { for(int i=1; i<=n; i++) { dis[i] = 0; head[i] = -1; vis[i] = 0; }}void add(int u,int v,int w) { e[cnt].v = v; e[cnt].nex = head[u]; e[cnt].w = w; head[u] = cnt++;}void dfs1(int u,int fa) { for(int i=head[u]; ~i; i=e[i].nex) { int to = e[i].v; if(to == fa) continue; dfs1(to,u); sumNode[u] += sumNode[to]; sumVal[u] += sumVal[to]; dis[u] += dis[to] + sumNode[to] * e[i].w; disval[u] += disval[to] + sumVal[to] * e[i].w; } ++ sumNode[u]; sumVal[u] += a[u];}void dfs2(int u,int fa) { for(int i=head[u]; ~i; i=e[i].nex) { int to = e[i].v; if(to == fa) continue; dis[to] = dis[u] - e[i].w * sumNode[to] + e[i].w * (n - sumNode[to]); disval[to] = disval[u] - e[i].w * sumVal[to] + e[i].w * (totval - sumVal[to]); dfs2(to,u); }}int main() { n = read; m = n - 1;// init(); Clear(dis,0); Clear(disval,0); Clear(sumVal,0); Clear(sumNode,0); Clear(head,-1); for(int i=1; i<=n; i++) { a[i] = read; totval += a[i]; } for(int i = 1; i<=m; i++) { int u = read,v = read,w = read; add(u,v,w); add(v,u,w); } dfs1(1,0); dfs2(1,0); for(int i=1; i<=n; i++) { printf("%lld\n",dis[i] * a[i] + disval[i]); } return 0;}

参考

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。