博客

HDU-2196


本题大意是求取一颗无根树上每一个节点，到树上其余任意节点的最远距离

其实我们可以考虑利用树的直径的性质，我们假设树的直径的两个端点为

A

与

B

那么，树上任意节点

C

到树上其余任何节点的最远距离一定是

C->A

或者是

C->B


利用这个性质，我们只需利用3次dfs，

第一次是为了求取直径的

A

端点

第二次是为了求取其余所有点到

A

端点的距离，顺便可以求取

B

端点

最后我们可以再求取一次所有点到

B

端点的距离

对于每一个节点我们可以记录一个 ans[i]=max（ans[i],sum[i]）

这样就可以保证求出答案的正确性

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <vector>
#include <stack>
#include <set>
#include <string>
#define ls k*2
#define rs k*2+1
#define int long long
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int HASH=131;


struct node
{
    int to,val;
    node(int a,int b):to(a),val(b){};
};

vector<node> v[maxn];
int ans[maxn];
int sum[maxn];
int maxx=0;
int id=0;

void dfs(int u,int father)
{
    if(maxx<sum[u])
    {
        maxx=sum[u];
        id=u;
    }
    for(int i=0;i<v[u].size();i++)
    {
        node tmp=v[u][i];
        if(tmp.to==father) continue;
        sum[tmp.to]=sum[u]+tmp.val;
        ans[tmp.to]=max(sum[tmp.to],ans[tmp.to]);
        dfs(tmp.to,u);
    }
    return;
}


signed main()
{
    int n;
    while(scanf("%lld",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=2;i<=n;i++)
        {
            int x,val;
            scanf("%lld %lld",&x,&val);
            v[i].push_back(node(x,val));
            v[x].push_back(node(i,val));
        }
        for(int i=1;i<=n;i++)
        {
            sum[i]=0;
            ans[i]=0;
        }
        maxx=0;
        dfs(1,1);
        for(int i=1;i<=n;i++)
            sum[i]=0;
        maxx=0;
        dfs(id,id);
        for(int i=1;i<=n;i++)
            sum[i]=0;
        maxx=0;
        dfs(id,id);
        for(int i=1;i<=n;i++)
        {
            printf("%lld\n",ans[i]);
        }
    }
    return 0;
}