【HDU 2196】 Computer(树的直径)
题链http://acm.hdu.edu.cn/showproblem.php?pid=2196
这题可以用树形DP解决，自然也可以用最直观的方法解，先求出树的直径，那么树的任意节点的最远点必然是直径上的两个端点之一，证明可以通过反证法构造：
设端点为a,b;设任意点为i,假设存在一点c到i的距离大鱼i到a,b的距离，那么a与c又能形成一个距离更长的点对，与ab是直径的假设不符，因此不存在c，证明完成。
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define inf 10000000000000
#define mod 1000000007
using namespace std;
ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e4+10;
const int M=2e4+10;
struct Edge{
int cost,to,nxt;
}Path[M];
int last[N],cnt;
void Addedge(int u,int v,int w){
Path[cnt]=(Edge){w,v,last[u]};
last[u]=cnt++;
}
int q[N*2],d[N],X;
void bfs(int x)
{
X=0;
int head=0,tail=1;
q[0]=x;
memset(d,0,sizeof(d));
d[x]=1;
while(head!=tail){
int cur=q[head];
head++;
if(d[cur]>d[X]) X=cur;
for(int i=last[cur];i;i=Path[i].nxt){
int v=Path[i].to;
if(!d[v]&&v!=x){
d[v]=d[cur]+Path[i].cost;
q[tail++]=v;
}
}
}
}
void Init()
{
memset(last,0,sizeof(last));
cnt=1;
}
int d2[N];
int main()
{
int n;
while(~scanf("%d",&n)){
Init();
for(int v=2;v<=n;v++){
int u=read(),w=read();
Addedge(u,v,w);
Addedge(v,u,w);
}
bfs(1);int ans1=X;
bfs(X);int ans2=X;
for(int i=1;i<=n;i++) d2[i]=d[i]-1;
bfs(X);
for(int i=1;i<=n;i++){
printf("%d\n",max(d[i]-1,d2[i]));
}
}
return 0;
}