代码(待加解释) hdu2196

发布时间 2023-09-04 22:19:41作者: Noname_min
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+10;
#define ll long long
int head[maxn],ver[maxn],nxt[maxn],edge[maxn];
int tot;
ll f[maxn][3];
int rx[maxn];

void dfs1(int x,int fa)
{
    for(int i=head[x]; i; i=nxt[i])
    {
        int y=ver[i];
        int w=edge[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(f[x][0]<=f[y][0]+w)
        {
            f[x][1]=f[x][0];
            f[x][0]=f[y][0]+w;
            rx[x]=y;

        }
        else if(f[y][0]+w>f[x][1])
            f[x][1]=f[y][0]+w;
        else if(f[y][1]+w>f[x][1])
            f[x][1]=f[y][1]+w;
    }
}

void dfs2(int x,int fa)
{

    for(int i=head[x]; i; i=nxt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        int w=edge[i];
        if(rx[x]==y)
            f[y][2]=max(f[x][1]+w,f[x][2]+w);
        else
            f[y][2]=max(f[x][0]+w,f[x][2]+w);
        dfs2(y,x);
    }
}
void add(int u,int v,int w)
{
    edge[++tot]=w;
    ver[tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        tot=0;
        memset(f,0,sizeof(f));
        memset(rx,0,sizeof(rx));
        memset(head,0,sizeof(head));
        for(int i=2; i<=n; i++)
        {
            int v,w;
            scanf("%d%d",&v,&w);
            add(i,v,w);
            add(v,i,w);
        }
        dfs1(1,1);
        dfs2(1,1);
        for(int i=1; i<=n; i++)
        {
            printf("%lld\n",max(f[i][0],f[i][2]));
        }
    }
}