51nod 1405 树的距离之和 （树形dp）

51nod 1405 树的距离之和 （树形dp）

Description

给定一棵无根树，假设它有n个节点，节点编号从1到n ，求任意两点之间的距离（最短路径）之和。

Input

第一行包含一个正整数n (n <= 100000)，表示节点个数。后面(n - 1)行，每行两个整数表示树的边。

Output

每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。

Input示例

41 23 24 2

Output示例

5355

思路

我们选定节点 1 为树根， des[i] 代表以 i 为根的子树的节点个数， ans[i] 代表所有节点到 i

对于根节点来说， ans[1] 等于所有节点的深度之和，于是我们可以先求得 ans[1]

随后对于 x 的子节点 to 来说， ans[to]=ans[x]−des[to]+(n−des[to])

其中 −des[to] 是因为以 to 为根的子树中所有点距离 to 比 距离 x 少 1 ，+(n−des[to]) 指其余点距离 to 比距离 x 多 1

AC 代码

#includeusing namespace std;typedef __int64 LL;const int maxn = 1e5+10;struct node{ int to; int next;} edge[maxn<<1];int head[maxn],tot,n;int des[maxn];LL ans[maxn];void init(){ memset(ans,0,sizeof(ans)); memset(des,0,sizeof(des)); memset(head,-1,sizeof(head)); tot=0;}void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++;}void dfs1(int x,int fa,int deep){ des[x]=1; ans[1]+=deep; for(int i=head[x]; i!=-1; i=edge[i].next) { int to=edge[i].to; if(to!=fa) { dfs1(to,x,deep+1); des[x]+=des[to]; } }}void dfs2(int x,int fa){ for(int i=head[x]; i!=-1; i=edge[i].next) { int to=edge[i].to; if(to!=fa) { ans[to] = ans[x]-des[to]+(n-des[to]); dfs2(to,x); } }}int main(){ ios::sync_with_stdio(false); init(); cin>>n; for(int i=1; i>u>>v; addedge(u,v); addedge(v,u); } dfs1(1,-1,0); dfs2(1,-1); for(int i=1; i<=n; i++) cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。