acw325.计算机

题意：

• 一所学校前段日子买了第一台计算机，ID是1。
• 之后学校又买了N-1台计算机。
• 每台新计算机都与之前买进的其中一台相连。
• 请你求出第$i$台计算机到其最远的计算机的电缆长度。

思路：

换根。
还是很明显的换根$dp$的。
设$f(i,0/1/2)$。
为什么要这么做呢？
0表示以$i$为根节点的子树最远能到达的距离是多少。
1表示以$i$为根节点的子树次远能到达的距离是多少。
但距离不一定是往下走，也有可能是要往上走的。
要怎么求呢？那这时候就有两种情况了：
$f(i,2)$表示$i$节点到他的父节点$j$的答案。
1：如果$i$的父节点的正向最大距离不经过$i$的话，那么$f(i,2)$要不就是他父节点的反向最大距离+$w$，要不就是他父节点正向经过最大距离+$w$。
2：如果$i$的父节点的正向最大距离经过$i$的话，那么$f(i,2)$要么就是他父节点反向最大距离+$w$，要不就是他父节点的正向经过次大距离+$w$。
如果不理解可以画个图，或者底下留言
每个节点的答案是$max(f(x,0),f(x,2))$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 20;
int n, f[maxn][4], longest[maxn];
int head[maxn], nex[maxn<<1], edge[maxn<<1], ver[maxn<<1], tot;
inline void add_edge(int x, int y, int z){
    ver[++tot] = y; edge[tot] = z;
    nex[tot] = head[x]; head[x] = tot;
}

void init()
{
    tot = 0;
    for(int i = 0; i <= n+10; i++) 
    {
        head[i] = 0;
        f[i][1] = f[i][2] = f[i][0] = -1;
        longest[i] = 0;
    }        
}

//求最大值和次大值
int dfs1(int x, int fa)
{
    if(f[x][0] >= 0) return f[x][0];
    f[x][0] = f[x][1] = f[x][2] = longest[x] = 0;
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i], z = edge[i]; 
        if(y == fa) continue;
        if(f[x][0] < dfs1(y, x) + z)
        {
            f[x][1] = f[x][0];
            f[x][0] = dfs1(y, x) + z;
            longest[x] = y;
        }
        else if(f[x][1] < dfs1(y, x) + z)
            f[x][1] = dfs1(y, x) + z;
    }
    return f[x][0];
}

void dfs2(int x, int fa)
{
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i], z = edge[i];
        if(y == fa) continue;
        if(y == longest[x]) f[y][2] = max(f[x][1], f[x][2]) + z;
        else f[y][2] = max(f[x][0], f[x][2]) + z;
        dfs2(y, x);
    }
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        init();
        for(int x = 2, y, z; x <= n; x++)
        {
            scanf("%d%d", &y, &z);
            add_edge(x, y, z);
            add_edge(y, x, z);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        for(int i = 1; i <= n; i++)
            printf("%d\n", max(f[i][0], f[i][2]));
    }
    return 0;
}