首页 > 代码库 > 51 nod 1405 树的距离之和

51 nod 1405 树的距离之和

 

1405 树的距离之和技术分享

基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
 
给定一棵无根树,假设它有n个节点,节点编号从1到n, 求任意两点之间的距离(最短路径)之和。
Input
第一行包含一个正整数n (n <= 100000),表示节点个数。后面(n - 1)行,每行两个整数表示树的边。
Output
每行一个整数,第i(i = 1,2,...n)行表示所有节点到第i个点的距离之和。
Input示例
41 23 24 2
Output示例
5355

 

 

/*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 <algorithm>#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <vector>#include <math.h>#include <queue>#include <set>#include <map>#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<class T> 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<class T> 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]);        }    }}

  

51 nod 1405 树的距离之和