hdu 2196 computer 求树上的随意最远点对 O（n）

题意：

给定n个结点，他们之间用n-1条边链接（这一点说明这个图的形状 就是一棵树 无环），给你一个结点，距离此节点最远的点与这个节点之间的距离。

解题思路：

经典的树上最长点对问题。不过带权，但是解决方法没有区别

首先找任意一个点，dfs()求出距离这个点的最远点END1 O(n)

然后从END1出发 再次dfs() 求出距离END1的最远点 期间经过每一个结点时，更新dist[i] （这个状态表示距离结点i的最远点到它的距离） 然后求出END2

从END2 再次出发 再遍历一遍所有结点 再次更新dist[i];

明确一个性质：可以证明 对于任意一个节点 距离它最远的结点 一定是END1 或 END2 。

code：

#include<cstdio>#include<cstring>#include<cstring>#include<vector>#include<algorithm>using namespace std;//#pragma comment(linker, "/STACK:102400000,102400000")const int maxn = 10005;vector<int> g[maxn];vector<int> cost[maxn];int dist[maxn];int END,max_;int n;void init(){    for(int i = 0; i <= maxn; i++){        g[i].clear();        cost[i].clear();    }    for(int i = 2; i <= n; i++){        int u,w;        scanf("%d%d",&u, &w);        g[i].push_back(u);        cost[i].push_back(w);        g[u].push_back(i);        cost[u].push_back(w);    }}void dfs(int u, int fa, int len){    dist[u] = max(dist[u], len);    for(int i = 0; i < g[u].size(); i++){        int v = g[u][i];        int w = cost[u][i];        if(v == fa) continue;        dfs(v, u, len + w);    }    if(len >= max_){        END = u;        max_ = len;    }}void solve(){    memset(dist, 0, sizeof(dist));    max_ = 0;    dfs(1, -1, 0);    max_ = 0;    dfs(END, -1, 0);    max_ = 0;    dfs(END, -1, 0);    for(int i = 1; i <= n; i++){        printf("%d\n",dist[i]);    }}int main(){    while(scanf("%d",&n) != EOF){        init();        solve();    }    return 0;}

后来交上题目，返回RE....简直无情 

卧槽我居然傻逼手动扩栈。。。扩栈。。。栈。。简直无情 当然是毫无悬念的MT了...

实际上是我没有每次清空vector 。 忘了爱