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

Each city in Treeland has its own tax on prizes: ti. Let du,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 (tu+tv)du,v

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】

5
2 5 3 4 1
1 2 2
2 4 5
4 3 3
5 2 6

【样例2】

6
4 3 3 4 3 3
1 3 2
2 1 1
1 4 6
4 5 6
6 4 2

样例输出

【样例1】

130
159
191
163
171

【样例2】

209
206
232
209
336
232

首先先把花费P的式子拆开，我们可以得到p _{u , v} = ( t [ u ] + t [ v ] ) ∗ d _{u , v} = t [ u ] ∗ d _{u , v} + t [ v ] ∗ d _{u , v,}  其中d _{u , v} 表示两点之间的距离

关于几个数组：

dis[]：dis[x]表示除x之外所有节点与x之间的距离之和

disval[]：disval[x]表示除x之外所有节点到x之间的距离与给定权值的乘积的和

假设要求u uu到其他点花费的总和，那么P [ u ] = t [ u ] ∗ ∑ _v d _{u , v} + ∑ _v ( t [ v ] ∗

d _{u , v} ) ,令d i s [ u ] = ∑ _v d _{u , v ,} disval[u] =∑ _v(t[v]∗d _u,v)， 则P_u=t[u]∗dis[u]+disval[u]

我们可以先预处理出以u 为根的子树中节点到u uu点的距离总和以及以u uu为根的子树中节点到u 点的距离与点权乘积之和。

假设父节点为x，子节点为y ，用wx,y来表示x,y之间的边权 则预处理的转移方程为dis[x]=dis[y]+sumNode[y]\ ∗\ w_{x,y} ，这里的sumNode[]数组指的是子树中节点的数量。disval[x]=disval[y]+sumVal[y] ∗ w _x,y

，这里的sumVal数组指的是子树中节点点权之和。然后通过换根dp的方式，转移出dis[],disval[]数组。假设父节点为x，子节点为y，转移方程为dis[y]=dis[x]−sumNode[y] ∗ w _x,y+(n−sumNode[y]) ∗ w _x,y ，这里的n指的是节点的数量。

disval[y] = disval[x] - sumVal[y]\ ∗\ w_{x,y} + (totval - sumVal[y]) ∗ w_x,y

，这里的totval指的是所有节点的点权总和

理顺一下思路，就是先预处理出sumNode, sumVal ,dis, disval四个数组，然后再通过树形dp的方式更新 dis, disval 两个数组，最后再通过转移方程得到结果

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<int,int> 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;
}

参考

https://blog.csdn.net/weixin_43634220/article/details/108916701

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成8116 人正在系统学习中