免费手机网站制作,做网站爱游戏,一起做的网站,企业级网站开发1405 树的距离之和 基准时间限制#xff1a;1 秒 空间限制#xff1a;131072 KB给定一棵无根树#xff0c;假设它有n个节点#xff0c;节点编号从1到n, 求任意两点之间的距离#xff08;最短路径#xff09;之和。Input第一行包含一个正整数n (n 100000)#xff0c… 1405 树的距离之和 基准时间限制1 秒 空间限制131072 KB 给定一棵无根树假设它有n个节点节点编号从1到n, 求任意两点之间的距离最短路径之和。 Input 第一行包含一个正整数n (n 100000)表示节点个数。
后面(n - 1)行每行两个整数表示树的边。 Output 每行一个整数第i(i 1,2,...n)行表示所有节点到第i个点的距离之和。 Input示例 4
1 2
3 2
4 2 Output示例 5
3
5
5思路:dfs先选一个根节点然后dfs求出所有点到这个点的距离最小值之和过程中d[]记录当前点下所有子节点到这个点的最小距离之和node[]记录当前的点有多少个子节点包括本身。然后这样根节点的答案就有了然后他的子节点可以根据根节点来更新的得到d[n]d[m]-(d[n]node[n])node[m]-node[n];然后dfs一遍就可以更新了。 1 #includestdio.h2 #includealgorithm3 #includeiostream4 #includestring.h5 #includestdlib.h6 #includequeue7 #includeset8 #includevector9 #includemap
10 using namespace std;
11 typedef long long LL;
12 vectorintvec[100005];
13 LL d[100005];
14 LL node[100005];
15 bool flag[1000005];
16 void dfs(int n);
17 void slove(int n);
18 int main(void)
19 {
20 int n;
21 scanf(%d,n);
22 int i,j;
23 for(i 0; i n-1; i)
24 {
25 int x;
26 int y;
27 scanf(%d %d,x,y);
28 vec[x].push_back(y);
29 vec[y].push_back(x);
30 }
31 memset(flag,0,sizeof(flag));
32 memset(d,0,sizeof(d));
33 dfs(1);
34 memset(flag,0,sizeof(flag));
35 slove(1);
36 for(i 1; i n; i)
37 printf(%lld\n,d[i]);
38 return 0;
39 }
40 void dfs(int n)
41 {
42 node[n];
43 flag[n] true;
44 int i,j;
45 for(i 0; i vec[n].size(); i)
46 {
47 int x vec[n][i];
48 if(!flag[x])
49 {
50 dfs(x);
51 node[n]node[x];
52 d[n]d[x];
53 d[n]node[x];
54 }
55 }
56 }
57 void slove(int n)
58 {
59 flag[n] true;
60 int i;
61 for(i 0; i vec[n].size(); i)
62 {
63 int x vec[n][i];
64 if(!flag[x])
65 {
66 LL y node[n]-node[x];
67 d[x] d[n] - (d[x] node[x])y;
68 node[x]y;//printf(%d %lld\n,x,d[x]);
69 //flag[x] true;
70 slove(x);
71 }
72 }
73 } 转载于:https://www.cnblogs.com/zzuli2sjy/p/5932118.html
