题目描述

题目大意：

给出一棵树，求对于每个点，找到树中与该点之间距离最大的某个点，询问距离

题目分析：

对于每个点 和它距离最长的点只可能在父树里或者是在子树里
所以 fasum[x]表示x的父树到点x的最大距离 g[x]表示点x子树中的点到x的最大距离
所以g[x]=val[i]+max{g[to[i]]}
对于 fasum[x] 有两种可能 从它父亲的父树里来 或者是他的某个兄弟的子树里的点
所以fasum[x]=max(fasum[fa[x]],g[fa[x]])
但是有问题 如果g[fa[x]]是从x的子树里来的 那就糟了 所以还要记录子树次大值
这样就AC了这道题 并使用结构体来存储子树最大值和子树次大值

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k,p,q;
int head[100000];
int val[100000];
int to[100000];
int net[100000];
struct your
{
    int big;
    int biger;
    int big_num;
    int biger_num;
}dis[100000];
int fasum[100000];
int tot;
void add(int x,int y,int c)
{
    net[++tot]=head[x];
    to[tot]=y;
    val[tot]=c;    
    head[x]=tot;
}
void dfs1(int x,int temp)
{    
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==temp) continue;
        dfs1(to[i],x);
        if(dis[x].biger<dis[to[i]].biger+val[i])
        {
            dis[x].big=dis[x].biger;
            dis[x].big_num=dis[x].biger_num;
            dis[x].biger=dis[to[i]].biger+val[i];
            dis[x].biger_num=to[i];
            continue;
        }
        if(dis[x].big<dis[to[i]].biger+val[i])
        {
            dis[x].big=dis[to[i]].biger+val[i];
            dis[x].big_num=to[i];
        }
    }
}
int check(int x,int temp,int c)
{
    int tmp=fasum[temp];
    if(tmp<dis[temp].biger&&dis[temp].biger_num!=x)
        tmp=dis[temp].biger;
    if(tmp<dis[temp].big&&dis[temp].big_num!=x)
        tmp=dis[temp].big;
    return tmp+c;
}
void dfs2(int x,int temp,int c)
{
    fasum[x]=check(x,temp,c);
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==temp) continue;
        dfs2(to[i],x,val[i]);
    }
    return ;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<n;i++)
        {
            int x,y,c;
            scanf("%d%d",&y,&c);
            add(i+1,y,c);
            add(y,i+1,c);
        }
        dfs1(1,0);
        dfs2(1,0,0);
        for(int i=1;i<=n;i++)
            printf("%d\n",max(dis[i].biger,fasum[i]));
        memset(head,0,sizeof head);
        memset(val,0,sizeof val);
        memset(to,0,sizeof to);
        memset(dis,0,sizeof dis);
        memset(net,0,sizeof net);
        tot=0;
        memset(fasum,0,sizeof fasum);
    }
    return 0;
}