51 nod 1405 树的距离之和

1405 树的距离之和51 nod 1405 树的距离之和

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

  

上一篇:判断iframe加载完成、用于当ifame加载完成时执行一些操作


下一篇:python浅谈正则的常用方法