http://acm.hdu.edu.cn/showproblem.php?pid=2196

树型DP

类似树的直径的\(dp\)构造方式

\[dp[u][0]表示以u为根的子树中的最长链\\
dp[u][1]表示以u为根的子树中的次长链(可以与最长链相等)\\
up[u]表示从u到非子树的最长链\\
dp数组一个dfs预处理\\
up[u]要么从其父亲的非子树的最长链转移而来，要么从其父亲的其他子节点转移而来
\]

还是比较容易实现的

\(C++ Code:\)

#include
#include
#include
#include
#define N 20005
using namespace std;
int head[N],d1[N],d2[N],nxt[N];
int n,x,y,tot;
int dp[N][2],up[N];
void add(int x,int y,int z)
{
tot++;
d1[tot]=y,d2[tot]=z;
nxt[tot]=head[x],head[x]=tot;
}
void dfs(int u,int f)
{
for (int i=head[u];i;i=nxt[i])
{
int v=d1[i];
int cost=d2[i];
if (v==f)
continue;
dfs(v,u);
if (dp[v][0]+cost>=dp[u][0])
{
dp[u][1]=dp[u][0];
dp[u][0]=dp[v][0]+cost;
} else
dp[u][1]=max(dp[u][1],dp[v][0]+cost);
}
}
void Clear()
{
memset(dp,0,sizeof dp);
memset(up,0,sizeof up);
memset(head,0,sizeof head);
tot=0;
}
void Getans(int u,int f)
{
for (int i=head[u];i;i=nxt[i])
{
int v=d1[i];
int cost=d2[i];
if (v==f)
continue;
if (dp[u][0]==dp[v][0]+cost)
up[v]=max(up[u],dp[u][1])+cost; else
up[v]=max(up[u],dp[u][0])+cost;
Getans(v,u);
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
Clear();
for (int i=2;i<=n;i++)
{
scanf("%d%d",&x,&y);
add(i,x,y);
add(x,i,y);
}
dfs(1,0);
Getans(1,0);
for (int i=1;i<=n;i++)
printf("%d\n",max(up[i],dp[i][0]));
}
return 0;
}