【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#include #include #include #include #include #include #include #define ll long long#define inf 10000000000000#define mod 1000000007using 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;}