HDU 2196 Computer 樹上最長距離

題意：一個樹形的網絡傳輸結構，求出每個節點的最遠距離。

思路：

首先有一個結論：樹上任意一個節點的最遠距離對應的節點，一定是樹的直徑的兩個端點之一。

證明如下：

設樹的直徑的兩個端點為u,v，設任意一點為w。

1.當w位于 u→v  的路徑上時，w的最遠距離對應的點顯然是點u或者是點v.

2.當w不在 u→v  的路徑上時，我們利用反證法來證明上面的結論。

假設w的最遠距離對應的點是s，則 L w→s >L w→v  

必然可以找到一個點t，在 w→t  的路徑上，路徑 w→v  和路徑 w→s  是重合的。

則

L w→s >L w→v  

L w→t +L t→s >L w→t +L t→v  

L t→s >L t→v  

我們再引入直徑的另外一點u

L u→t +L t→s >L u→t +L t→v  

L u→s >L u→v  

和 u→v  為樹的直徑相沖突。

是以假設不成立。

這樣利用上面的結論，選取任意節點為根，一遍DFS就能求出直徑的一個端點，然後從這個端點再次DFS就能求出另外一個端點，最遠距離每個節點到兩個端點距離的最大值。

代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = ;

struct edge{
    int to,w;
    edge(){}
    edge(int t, int ww):to(t),w(ww){}
} edges[MAX<<];

int N;
int nxt[MAX<<],head[MAX],tot;
int dp1[MAX],dp2[MAX];


void init()
{
    memset(head,-,sizeof(head));
    tot = ;
}

void addedge(int u, int v, int w)
{
    edges[tot] = edge(v,w);
    nxt[tot] = head[u];
    head[u] = tot++;
}

void dfs(int u, int p, int d, int* dis)
{
    dis[u] = d;
    for(int i = head[u]; ~i; i = nxt[i]){
        edge & e = edges[i];
        if(e.to == p) continue;
        dfs(e.to,u,d+e.w,dis);
    }
}


int main(void)
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&N) != EOF){
        init();
        for(int i = ; i <= N; ++i){
            int v,w;
            scanf("%d%d",&v,&w);
            addedge(i,v,w);
            addedge(v,i,w);
        }
        dfs(,,,dp1);
        int poi1 = , len = ;
        for(int i = ; i <= N; ++i){
            if(dp1[i] > len){
                len = dp1[i];
                poi1 = i;
            }
        }
        dfs(poi1,,,dp1);
        int poi2 = ;len = ;
        for(int i = ; i <= N; ++i){
            if(dp1[i] > len){
                len = dp1[i];
                poi2 = i;
            }
        }
        dfs(poi2,,,dp2);
        for(int i = ; i <= N; ++i)
            printf("%d\n",max(dp1[i],dp2[i]));
    }
    return ;
}