首页 > 代码库 > 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 树的距离之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。