题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196
题意是n台电脑,n-1条边,输出第距离i台电脑最远的距离是多少。
思路就是不管那一台电脑,距离它最远距离的一定是树的直径的两个端点的其中一个,所以我们只需要求出树的直径的两个端点,然后再求出这两个端点到每个点的距离就好了,然后输出的时候比较一下就可以了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 20005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int to,next,w;
}Edge[maxn];
int head[maxn],num;
int dist[maxn], pre[maxn];
bool vis[maxn];
int T,n,m;
void init(){
for(int i=0;i<=n;i++){
head[i] = -1;
}
num = 0;
}
void add(int u,int v,int w){
Edge[num].to = v;
Edge[num].w = w;
Edge[num].next = head[u];
head[u] = num ++;
}
void bfs(int x){
queue<int> q;
memset(dist,0,sizeof(dist));
memset(vis,false,sizeof(vis));
q.push(x);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = true;
for(int i=head[u];i!=-1;i=Edge[i].next){
int to = Edge[i].to;
if(vis[to] == false){
vis[to] = true;
dist[to] = dist[u] + Edge[i].w;
q.push(to);
}
}
}
}
int main()
{
while(~scanf("%d",&n)){
init();
for(int i=2;i<=n;i++){
int v, w;
scanf("%d%d",&v,&w);
add(i, v, w);
add(v, i, w);
}
bfs(1);
int Max = 0;
int pos = 0;
for(int i=1;i<=n;i++){
if(Max < dist[i]){
Max = dist[i];
pos = i;
}
}
bfs(pos);
Max = 0;
for(int i=1;i<=n;i++){
if(Max < dist[i]){
Max = dist[i];
pos = i;
}
pre[i] = dist[i];
}
bfs(pos);
for(int i=1;i<=n;i++){
printf("%d\n", max(pre[i], dist[i]));
}
}
return 0;
}