求出每个节点到到其他所有节点的距离之和
先dfs(1)预处理求出每个节点所在的子树的节点数量(包含本身)
再通过树形dp求解
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
const int N=1000050;
int n,u,v;
int cnt;
int head[N];
struct Edge{
int v,next;
}edge[N];
int num[N];
ll dp[N];
bool vis[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v){
edge[cnt]=Edge{
v,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{
u,head[v]};
head[v]=cnt++;
}
void dfs(int u,int d){
//num数组保存u节点所在子树的节点数(包括本身)
vis[u]=true;
num[u]=1;
//先选定1为根
//dp数组表示节点到其他节点的距离之和
//对根而言距离也就是各节点的深度
dp[1]+=d;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(!vis[v]){
dfs(v,d+1);
num[u]+=num[v];
}
}
}
void solve(int u){
vis[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(!vis[v]){
//v是u的子节点,v到所有节点的距离dp[v]就比u到所有节点的距离dp[u]少num[v]
//同时还要多上父节点u的其他子树的距离n-num[x]
dp[v]=dp[u]+(n-num[v])-num[v];
solve(v);
}
}
}
int main(void){
scanf("%d",&n);
init();
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
memset(vis,false,sizeof(vis));
dfs(1,0);
for(int i=1;i<=n;i++){
printf("%d %d\n",i,num[i]);
}
memset(vis,false,sizeof(vis));
solve(1);
for(int i=1;i<=n;i++){
printf("%lld\n",dp[i]);
}
return 0;
}