题目链接
https://www.qduoj.com/problem/80
题目大意
n个节点，相连节点距离为1，顺序输出每个节点距离其他节点的距离之和。
举个例子：
假如构造的树是这样的，因为要按照节点序号输出，所以我们先以1号节点为根节点。
那输出的结果应该为
15 //15 = (9->1 = 1) + (6->1 = 1) + (5->1 = 2) + (3->1 = 2) + (4->1 = 2) + (8->1 = 2) + (2->1 = 2) + (7->1 = 3) 25 //25 = (6->2 = 1) + (8->2 = 2) + (1->2 = 2) + (9->2 = 3) + (5->2 = 4) + (3->2 = 4) + (4->2 = 4) + (7->2 = 5) 19 //…… 21 21 18 26 25 14
解题思路
两次深搜。
第一次深搜
变量介绍
参数x表示当前节点，参数fa表示其父节点，局部变量p表示x的子节点；
cnt[i]表示以i为根节点的子树上（包含根节点）节点的数量（在第一次深搜里，cnt数组的含义暂时是这样的）；
sum[i]表示以i为根节点的子树上所有点到i节点的距离和（在第一次深搜里，sum数组的含义暂时是这样的）
深搜目的
对cnt数组和sum数组进行初步赋值，含义正如上述。
深搜实现
以1节点为根节点开始深搜，不停地访问其子节点；
因为我们的目的是对cnt数组和sum数组初始化，它们（暂时）的含义分别是“以i为节点的子树的节点个数”和“以i为节点的子树中所有节点到根节点的距离和”，因此，我们想要对每个子树的根节点的cnt和sum赋值的话，就需要先把其子节点赋上值，才能算出根节点的cnt和sum值。自然，我们要先dfs到底，再通过递归返回进行赋值与加和，实现对cnt数组和sum数组的赋值；
//核心赋值语句： cnt[x]+=cnt[p];//对cnt赋值 sum[x]+=sum[p]+cnt[p]*1;//对sum赋值
已知p是x的子节点，cnt[x]代表以x为根节点的子树的节点数，它加上所有以x子节点为根节点的子树的全部节点就是以x为根节点子树的节点个数；sum[x]表示以x为根节点的子树上所有点到x节点的距离和，它加上所有以x子节点为根节点的子树的sum值，再加上以x子节点为根节点的子树的节点个数与距离的乘积，就得到了sum[x]。（语言表达太难了，直接上图！）
注意：cnt要初始化为1，因为每个点为根节点的子树，至少有自己本身这个节点，因此初始化为1；而本节点到本节点的距离为0，因此sum初始化为0。
还是上图中的树，
//cnt的赋值 cnt[1] = cnt[9] + cnt[6] + 1 //初始化的1 cnt[9] = cnt[5] + cnt[3] + cnt[4] + 1 cnt[3] = cnt[7] + 1 …… //sum的赋值 sum[1] = (sum[9] + cnt[9]*1) + (sum[6] + cnt[6]*1) //1是从9节点到1节点的距离，也是从6节点到1节点的距离 sum[9] = (sum[5] + cnt[5]*1) + (sum[3] + cnt[3]*1) + (sum[4] + cnt[4]*1) sum[3] = (sum[7] + cnt[7]*1)
cnt数组的赋值比较好理解，但是sum数组的赋值相对不好理解一些，看图吧！
可以理解为每个节点上都站着一个人，节点序号就是人的序号，计算sum[1]就是计算第2，3，4，5，6，7，8，9号人到1号人位置的距离和（走过的路程和），这就可以转化为绿框里的人先走到第9号人的位置，再和第9号人一起走到第1号人的位置，紫框里的人先走到第6号人的位置，再和第6号人一起走到第1号人的位置，这两部分和距离正是sum[1]。转换成代码，绿框里的人走到第9号人的位置的距离是sum[9]，紫框里的人走到第6号人的位置的距离是sum[6]，此时，绿框里的人已经与第9号人汇合了，紫框里的人已经与第6号人汇合了，然后红框里的人再一起从第9号人的位置出发，前往第1号人的位置，体现在代码上为cnt[9] * 1，含义为红框里的所有人前往第1号人的位置，蓝框里的人也一起从第6号人的位置出发，前往第1号人的位置，体现在代码上为cnt[6] * 1，含义为蓝框里的所有人前往第1号人的位置。综上，sum[1] = (sum[9] + cnt[9] * 1) + (sum[6] + cnt[6] * 1)，转移方程为sum[根节点] = (sum[子节点]+cnt[子节点] * 1)
第二次深搜
变量介绍
参数x表示当前节点，参数fa表示其父节点，局部变量p表示x的子节点；（同上）
cnt[i]在被更新前，表示以i为根节点的子树上（包含根节点）节点的数量（同上）；在被更新后，表示为以i节点为整棵树的根节点，所含节点的个数，即全部节点个数n；
sum[i]在被更新前，表示以i为根节点的子树上所有点到i节点的距离和（同上）；在被更新后，表示为全部节点到i节点的距离和。
深搜目的
这次深搜是为了刷新sum值，因为最终输出的是sum值。
cnt值的更新是为了刷新sum值才进行的。
深搜实现
以1节点为根节点开始深搜，不停地访问其子节点；
我们的目的是更新cnt数组和sum数组，它们（更新后）的含义分别是“表示为以i节点为整棵树的根节点，所含节点的个数”和“全部节点到i节点的距离和”。要更新的是p节点的sum和cnt值，而更新p节点的sum和cnt值需要利用x节点的sum和cnt值，因此，需要先更新完根节点的sum和cnt值，才能去更新子节点的sum和cnt的值。自然，我们要先更新sum和int，再dfs子节点；
到这里，你会发现（你应该没发现）第一个深搜每次的操作对象是x节点，而第二个深搜每次更新的对象是p节点，即x的子节点。
那么，为什么要更新的是p节点的值而不是x节点的值呢？？？
从第二次深搜开始说起吧，从1节点dfs进入，此时未更新的sum[1]表示的就是最终的sum[1]，也就是全部节点到1节点的距离，因为1节点是整棵树的根节点，它现在的sum值就是它最终的sum值。按照dfs的思想，我们每次知道的都是根节点最终的sum值，那就用这个最终值去更新其子节点的sum值。
每次更新完sum值之后，都要把子节点对应的cnt值赋值为其父节点的cnt值，即n，因为每一次dfs都是从1节点进入的，所以每一次cnt都被传递性地赋值为了n。这样做的目的是，把p节点当成整棵树的根节点，方便p的子节点sum值的更新。（看看转移方程就明白了）
//核心更新语句 sum[p]+=(sum[x]-sum[p]-cnt[p]*1)+(cnt[x]-cnt[p])*1; cnt[p]=cnt[x];
好长好麻烦的转移方程
还是以上图为例，
刚进入dfs时，p为第9号人的位置，x为第1号人的位置，fa=0不对应任何节点，欲求sum[p]，即全部人到第9号人位置的路程和，就需要用红框中人到第9号人位置的路程和加上蓝框中人到第9号人位置的路程和。其中，红框里的人到第9号人位置的距离和就是未更新时的sum值，因为红框刚好是9节点的子树除去根节点的部分；
而蓝框里的人到第9号人位置的路程和求起来就比较麻烦了，现在已知的条件是未更新的所有节点的cnt值和为最终答案的sum[1]，那我们就通过这些条件来求。sum[1] = 紫框里所有人走到第1号人位置的路程和 + 绿框里所有人走到第1号人位置的路程和，进一步分解，sum[1] = 红框里所有人走到第9号人位置的路程和 + 汇合在第9号人位置的所有人一起去第1号人位置的路程和 + 绿框里所有人走到第1号人位置的路程和，代码表示为，sum[1] = sum[9] + cnt[9] * 1 + 绿框里所有人到第1号人的路程和，进一步转化，绿框里所有人到第1号人的路程和 = sum[1] - sum[9] - cnt[9] * 1。见证奇迹的时刻，蓝框所有人到第9号人位置的路程和 = 绿框所有人到第1号人位置的路程和 + 汇合在第1号人位置的所有人一起去第9号人位置的路程和，把上述转化得到的方程代入得，蓝框所有人到第9号人位置的路程和 = (sum[1] - sum[9] - cnt[9] * 1) + (cnt[1] - cnt[9]) * 1。
因此，最终sum[9] = sum[9] + (sum[1] - sum[9] - cnt[9] * 1) + (cnt[1] - cnt[9]) * 1;
=>sum[9] += (sum[1] - sum[9] - cnt[9] * 1) + (cnt[1] - cnt[9])*1;
cnt的更新显得简单多了，就是重新换一个树根。
通过特例的讲解理解过程，接着再说一下一般形式，
整棵树被分成了4部分，p节点，x节点，与p相连部分，与x相连部分，且4部分相互独立共同构成整棵树。本质上，x与p不具有父子关系，但是sum和cnt对应的x和p存在父子关系，我们要做的就是通过cnt和sum求出最终的sum，其实也就是利用左红框区域与右红框区域的cnt与sum的关系计算出p节点的最终sum值，与树的形状无关。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
vector<int> a[N];
ll sum[N],cnt[N];
void dfs(int x,int fa){//初步构建sum和cnt数组
cnt[x]=1,sum[x]=0;
for(int i=0;i<a[x].size();i++){
int p=a[x][i];
if(p==fa) continue;
dfs(p,x);
cnt[x]+=cnt[p];
sum[x]+=sum[p]+cnt[p]*1;
}
}
void dfs1(int x,int fa){
for(int i=0;i<a[x].size();i++){
int p=a[x][i];
if(p==fa) continue;
sum[p]+=(sum[x]-sum[p]-cnt[p]*1)+(cnt[x]-cnt[p])*1;
cnt[p]=cnt[x];
dfs1(p,x);
}
}
int main(){
int n;
cin>>n;
memset(sum,0,sizeof sum);
memset(cnt,0,sizeof cnt);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,0);
dfs1(1,0);
for(int i=1;i<=n;i++)
cout<<sum[i]<<endl;
}我的错误代码
//我感觉挺对的，就是数组开不下，其实还是错的。。。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=99999999;
const int N=1e3+5;//这里开不下
int dis[N][N];
vector<int> e[N];
int dfs(int x,int y,int fa){
if(x==y) return dis[x][y]=0;
if(dis[x][y]!=INF) return dis[x][y];
for(int i=0;i<e[x].size();i++){
dis[x][e[x][i]]=1;
if(e[x][i]!=fa){
dis[x][y]=min(dis[x][y],dis[x][e[x][i]]+dfs(e[x][i],y,x));
dis[y][x]=dis[x][y];
}
}
return dis[x][y];
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=INF;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++){
ll sum=0;
for(int j=1;j<=n;j++){
dis[i][j]=dfs(i,j,0);
sum+=dis[i][j];
}
cout<<sum<<endl;
}
}总结
又是一道简单的难题，啥意思？就是说这个题可以变形成难题，但是基本思路不变。
我太菜了，根本不会，一个没过多久就会忘掉这种做法。
常回来看看，才能加深印象。
最后的最后，我还想再问一句：我什么时候才能成为大佬啊啊啊！！！
京公网安备 11010502036488号