题意
原题链接
给定 \(n\) 个点，需要在之间连接 \(n - 1\) 条边，每条边的颜色为红/蓝。连边规则为：设现在已经将 \(1\sim i-1\) 连接起来，则可以选择在 \(1\sim i-1\) 间的任意一个点与 \(i\) 连一条红边，或者将两个连接了红边的点 \(j,k\) 之间，将其红边删去，然后在 \(j,i\)、\(k,i\)之间连接两条蓝边。求蓝边长度的最大值。
赛时 0PTS
赛后
本题为在树上求最大值，因此考虑树形 DP。显然，本题为一棵无根树，因此我们需要使用二次扫描与换根法进行处理。
朴素树形 DP
状态设计：\(f_{u,j}\) 表示在以 \(1\) 为根节点的树中的以 \(u\) 为根节点的子树中，\(u\) 为蓝边中点（\(j=1\)）/ \(u\) 不为蓝边中点（\(j=0\)）的蓝边长度的最大值（注意：在这里，由于是一棵无根树，因此我们总是将两条蓝边置为 \(fa \to u \to son\) 的形式，而不会出现 \(son \to u \to son\) 的形式。）
状态转移：
\(f_{u,0}\) 较好计算，由于 \(u\) 不能作为蓝边的中点，因此，对于它的每个儿子 \(j\) 而言，要么 \(j\) 也不作为蓝边的中点，\(i \to j\) 是一条红边，此时最大值为 \(f_{j,0}\)；要么 \(j\) 作为蓝边的中点，\(i \to j\) 是一条蓝边，此时最大值为 \(f_{j,1} + w_{i\to j}\)。综上，
根据题意，可以得到，\(u\) 最多只会作为一对蓝边的中点。因此，对于 \(f_{u,1}\)，我们可以枚举每一条边，计算这条边为蓝边的最大值，即
\[f_{u,1}=f_{u,0} + \max_{j \in son} (f_{j,0} + w_{i\to j} - \max\{f_{j,0},f_{j,1} + w_{i\to j}\}) \]换根 DP
在朴素树形 DP 中，我们可以通过将不同的点作为根来进行暴力枚举，时间复杂度 \(O(n^2)\)。
为了将时间复杂度优化成 \(O(n)\)，我们需要再开一个数组 \(g_{u}\)，表示在以 \(u\) 为根节点的树中，蓝边长度的最大值。记 \(u\) 的父亲为 \(fa\)，我们观察以 \(1\) 为根节点和以 \(u\) 为根节点的两棵树，会发现转移方向从 \(u\to fa\) 变为了 \(fa\to u\)，我们只需要再次进行 DFS 处理这一部分的更改就可以实现 \(O(n)\) 的换根 DP 了，这就是二次扫描与换根法。
对于本题，我们需要计算以 \(fa\) 为根的树中，去除掉以 \(u\) 为根的子树后，\(fa\) 为蓝边中点 / \(fa\) 不为蓝边中点的蓝边长度的最大值，（将 \(u\) 和 \(fa\) 间连接一条边），这需要我们计算在以 \(fa\) 为根的树中，转移到的最大值，次大值，和转移最大值的点。再以此计算以 \(u\) 为根的树中，\(g\)，最大值，次大值和转移最大值的点即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200005, M = 400005, INF = 2e9;
int h[N], e[M], w[M], ne[M], idx;
int n;
int f[N][2];
int maxn[N], maxid[N], smaxn[N];
int g[N];
int maxun[N], maxuid[N], smaxun[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa){
maxn[u] = smaxn[u] = f[u][1] = -INF, maxid[u] = 0;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == fa) continue;
dfs(j, u);
f[u][0] += max(f[j][0], f[j][1] + w[i]);
}
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == fa) continue;
if (f[j][0] + w[i] - max(f[j][0], f[j][1] + w[i]) > maxn[u]){
maxid[u] = j;
smaxn[u] = maxn[u];
maxn[u] = f[j][0] + w[i] - max(f[j][0], f[j][1] + w[i]);
}
else smaxn[u] = max(smaxn[u], f[j][0] + w[i] - max(f[j][0], f[j][1] + w[i]));
}
f[u][1] = f[u][0] + maxn[u];
}
void dfs2(int u, int fa, int val){
if (u == 1) g[u] = f[u][0], maxun[u] = maxn[u], maxuid[u] = maxid[u], smaxun[u] = smaxn[u];
else {
int ffa0 = g[fa] - max(f[u][0], f[u][1] + val);
int ffa1;
if (u != maxuid[fa]) ffa1 = ffa0 + maxun[fa];
else ffa1 = ffa0 + smaxun[fa];
g[u] = f[u][0] + max(ffa0, ffa1 + val);
maxuid[u] = maxid[u], maxun[u] = maxn[u], smaxun[u] = smaxn[u];
if (ffa0 + val - max(ffa0, ffa1 + val) > maxun[u]){
maxuid[u] = fa;
smaxun[u] = maxun[u];
maxun[u] = ffa0 + val - max(ffa0, ffa1 + val);
}
else smaxun[u] = max(smaxun[u], ffa0 + val - max(ffa0, ffa1 + val));
}
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == fa) continue;
dfs2(j, u, w[i]);
}
}
int main(){
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i < n; i ++ ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
dfs2(1, -1, 0);
int ans = 0;
for (int i = 1; i <= n; i ++ ) ans = max(ans, g[i]);
printf("%d\n", ans);
return 0;
}