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

[51NOD1405] 树的距离之和（树DP）

2024-08-17 16:52:08   218人阅读

题目链接：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）


联系
我们