首页 > 代码库 > [51NOD1405] 树的距离之和(树DP)

[51NOD1405] 树的距离之和(树DP)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1405

(1)我们给树规定一个根。假设所有节点编号是0-(n-1),我们可以简单地把0当作根,这样下来父子关系就确定了。

(2)定义数组num[x]表示以节点x为根的子树有多少个节点,dp[x]是我们所求的——所有节点到节点x的距离之和。
(3)在步骤(1)中,其实我们同时可以计算出 num[x],还可以计算出每个节点的深度(每个到根节点0的距离),累加全部节点深度得到的其实就是是dp[0]。
(4) 假设一个非根节点x,它的父亲节点是y, 并且dp[y]已经计算好了,我们如何计算dp[x]?  
以x为根的子树中那些节点,到x的距离比到y的距离少1, 这样的节点有num[x]个。
其余节点到x的距离比到y的距离多1,这样的节点有(n - num[x])个。
于是我们有 dp[x] = dp[y] - num[x] + (n - num[x]) = dp[y] + n - num[x] * 2
因为树的根节点dp[0]在步骤(3)已经计算出来了,根据所有的父子关系和这个上式,我们可以按照顺序计算出整个dp数组。特别像多校的一道题,或者说这类题都很类似。
 1 #include <bits/stdc++.h>
 2 #include<ext/pb_ds/assoc_container.hpp>
 3 #pragma comment(linker, "/STACK:10240000,10240000")
 4 using namespace std;
 5 using namespace __gnu_pbds;
 6 
 7 typedef long long LL;
 8 const int maxn = 200100;
 9 vector<int> G[maxn];
10 LL num[maxn];
11 LL dp[maxn];
12 int n;
13 
14 LL dfs1(int u, int p, LL d) {
15   int cnt = 1;
16   num[u] = cnt;
17   dp[1] += d;
18   for(int i = 0; i < G[u].size(); i++) {
19     int v = G[u][i];
20     if(v == p) continue;
21     num[u] += dfs1(v, u, d+1);
22   }
23   return num[u];
24 }
25 
26 void dfs2(int u, int p) {
27   for(int i = 0; i < G[u].size(); i++) {
28     int v = G[u][i];
29     if(v == p) continue;
30     dp[v] = dp[u] + n - num[v] * 2;
31     dfs2(v, u);
32   }
33 }
34 
35 int main() {
36   //freopen("in", "r", stdin);
37   int u, v;
38   while(~scanf("%d", &n)) {
39     memset(num, 0, sizeof(num));
40     memset(dp, 0, sizeof(dp));
41     for(int i = 1; i <= n; i++) G[i].clear();
42     for(int i = 1; i < n; i++) {
43       scanf("%d%d",&u,&v);
44       G[u].push_back(v);
45       G[v].push_back(u);
46     }
47     dfs1(1, -1, 0);
48     dfs2(1, -1);
49     for(int i = 1; i <= n; i++) printf("%lld\n", dp[i]);
50   }
51   return 0;
52 }

 

[51NOD1405] 树的距离之和(树DP)