51 nod 1405 树的距离之和-白红宇

51 nod 1405 树的距离之和

阅读量：5892 次

发布时间：2019-06-19

本文共 2303 字，大约阅读时间需要 7 分钟。

1405 树的距离之和

基准时间限制：1 秒空间限制：131072 KB 分值: 40

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

Input

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

Output

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

Input示例

41 23 24 2

Output示例

/*51 nod 1405 树的距离之和problem:给定一棵无根树，假设它有n个节点，节点编号从1到n, 对于每个i求所有点到i的和。solve:假设已经知道了所有点到u的和, 对于它右儿子v的和,可以发现增加了Size[左子树]条uv边.减少了Size[v]条uv边所以先求出所有点到1的和,然后可以推出其它所有点hhh-2016/09/13-20:15:59*/#pragma comment(linker,"/STACK:124000000,124000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define lson i<<1#define rson i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define scanfd(a) scanf("%lf",&a)#define key_val ch[ch[root][1]][0]#define eps 1e-7#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const int maxn = 100110;template
               
                 void read(T&num){ char CH; bool F=false; for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar()); for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar()); F && (num=-num);}int stk[70], tp;template
                
                  inline void print(T p){ if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar('\n');}ll ans[maxn];struct node{ int to,next;}edge[maxn <<2];int tot,n;int head[maxn];int Size[maxn];ll f[maxn];void add_edge(int u,int v){ edge[tot].to = v,edge[tot].next = head[u],head[u] = tot ++;}void dfs(int u,ll len,int pre){ f[u] = len; Size[u] = 1; for(int i = head[u]; i != -1;i = edge[i].next ) { int v = edge[i].to; if(v == pre) continue; dfs(v,len+1,u); Size[u] += Size[v]; }}void solve(int u,ll tans,int pre){ ans[u] = tans; for(int i = head[u];i != -1;i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; ll t = n-Size[v]*2; solve(v, (ll)tans + t,u); }}void init(){ tot = 0; clr(head,-1);}int main(){ int u,v; while(scanfi(n) != EOF) { init(); for(int i = 1;i < n;i++) { scanfi(u),scanfi(v); add_edge(u,v); add_edge(v,u); } dfs(1,0,-1); ll ta = 0; for(int i =1;i <= n;i++) ta += f[i]; solve(1,ta,-1); for(int i = 1;i <= n;i++) { print(ans[i]); } }}