HDU 2196 Computer

题意：

给定一棵树，每条边都有边权，求每个点的在这棵树上能够去到的最远距离

如果做过换根dp的话这题就很好想了

想法就是：先从1开始dfs一遍，那么每个点往它子树方向走的答案就出来了，那么每个点还剩父亲方向的答案没计算，那么再dfs一遍，用父亲方向的答案去更新这个节点就行了

轻松列出方程，\(u\) 是当前节点，\(v\) 表示子节点，0表示从子树方向来的答案，2表示从父亲方向来的，\(val_{u,v}\) 表示 $ u \leftrightarrow v$ 这条边的边权
\[ f_{u,0}=\max \{ f_{v,0} \}+val_{u,v} \]
\(f_{u,2}\) 的转移由于是自己转移给子节点（自上往下转移），所以我们用 \(f_v=f_u...\) 的形式来写
\[ f_{v,2}=\max ( f_{u,2},f_{u,0})+val_{u,v} \]
能从 \(f_{u,0}\) 转移是因为你可以通过 \(u\) 节点走到另 \(u\) 的另一个子节点（不能是 \(v\) ）

那么这里就出现了一个问题，如果现在 \(f_{u,0}\) 的值是由 \(f_{v,0}\) 转移的，那么 \(f_{v,2}\) 的转移就会出现 \(v\rightarrow u \rightarrow v\) ，会重复算，这就不行

所以我们再第一次dfs的时候还要注意算一个次大值 \(f_{u,1}\) ，表示 \(u\) 节点从子树方向来的答案的次大值

第二次dfs转移的时候就算一下，如果发现 \(f_{u,0}\) 的值等于 \(f_{v,0}+val_{u,v}\) ，那么就要用 \(f_{u,1}\) 的值去更新 \(f_{v,2}\)

第 \(i\) 个点的答案就是 \(\max(f_{i,0},f_{i,2})\)

// This code writed by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=10050;
struct Edge
{
    int nxt,to,w;
}E[MaxN<<2];
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int hd[MaxN],en,n;
int f[MaxN][3];
inline void adde(int u,int v,int w)
{
    ++en;
    E[en]=(Edge){hd[u],v,w};
    hd[u]=en;
    return;
}
inline void checkmax(int &x,int y)
{
    if(x<y)
        x=y;
    return;
}
inline void dfs1(int u,int fa)
{
    f[u][1]=0xc0c0c0c0c0c0c0c0;
    vector<int> dr;
    for(int i=hd[u];~i;i=E[i].nxt)
    {
        reg int v=E[i].to;
        if(v==fa)
            continue;
        dfs1(v,u);
        dr.push_back(f[v][0]+E[i].w);
    }
    if(dr.size())
    {
        sort(dr.begin(),dr.end());
        f[u][0]=dr[(int)dr.size()-1];
        if((int)dr.size()>=2)
            f[u][1]=dr[(int)dr.size()-2];
    }
    return;
}
inline void dfs2(int u,int fa)
{
    for(int i=hd[u];~i;i=E[i].nxt)
    {
        reg int v=E[i].to;
        if(v==fa)
            continue;
        checkmax(f[v][2],f[u][2]+E[i].w);
        if(f[u][0]-E[i].w==f[v][0])
            checkmax(f[v][2],f[u][1]+E[i].w);
        else
            checkmax(f[v][2],f[u][0]+E[i].w);
        dfs2(v,u);
    }
    return;
}
inline void work()
{
    memset(hd,-1,sizeof hd);en=0;
    memset(f,0,sizeof f);
    reg int v,w;
    for(int i=2;i<=n;++i)
    {
        read(v);read(w);
        adde(i,v,w);
        adde(v,i,w);
    }
    dfs1(1,0);
    dfs2(1,0);
    /*
    for(int i=1;i<=n;++i)                            
    {
        printf("Node %3lld 1st %25lld 2nd %25lld  3rd %25lld\n",
            i,f[i][0],f[i][1],f[i][2]);
    }
    */
    for(int i=1;i<=n;++i)
        printf("%lld\n",max(f[i][0],f[i][2]));
    return;
}
signed main(void)
{
    while(cin>>n)
        work();
    return 0;
}

HDU 2196 Computer

原文：https://www.cnblogs.com/chinesepikaync/p/12401245.html