题目大意
给定一个无向树。有两个扫雪机可以任意选择出发终止点，可以走回头路。求两个扫雪机遍历整个树所需的最短路程。
解题思路
不妨先考虑只有一个扫雪机的情况。
我们知道，在无向树上从任意一个结点出发，将所有的边经过两遍，串成一个环，最终都能回到那个结点。就像这样：
这也就是这一个扫雪机遍历整个树的最坏情况。
但是所有的路我们都走了两遍，很明显我们并不需要这样做，也不需要回到起始节点。于是我们将这个环去除一条路径，剩下的边就构成了一条简单路径，也就是起点和终点不在一个点上的扫雪机路线。并且这个去除的路径一定不能同时包含原图中一条边的两个方向，否则扫雪机就不能到达所有结点。
那么，自然是去除的路径越长，扫雪机所需走的路程就越短。
显然，要去除的就是树的直径。去除后的路径就是一台扫雪遍历完整棵树所需最短路径。就像这样：
接下来就很好办了。既然一台扫雪机的情况我们已经得出，那么将其推广到两台扫雪机甚至 \(k\) 台扫雪机就都不是问题。
上面得出，去除一条最长路径就是一台扫雪机的最短路径，那么去除两条不相交的最长路径就是两台扫雪机的最短路径（相交了就同时去除了原图一条边的两个方向），去除 \(k\) 条不相交最长路径就是 \(k\) 台扫雪机的最短路径。
由此，解法已经得出。
代码实现
显然使用树形DP求解。
深搜这棵树，记录每个结点 \(u\) 的四个状态：
- \(f_1\)：以 \(u\) 为根的子树中，往 \(u\) 结点之上延伸的最长的一条路径
- \(f_2\)：以 \(u\) 为根的子树中，不往 \(u\) 结点之上延伸的最长的一条路径
- \(f_3\)：以 \(u\) 为根的子树中，往 \(u\) 结点之上延伸（当然只能延伸一条）的两条路径
- \(f_4\)：以 \(u\) 为根的子树中，不往 \(u\) 结点之上延伸的两条路径
如果是 \(k\) 台扫雪机，那么就继续往下以此类推。整棵树根 \(root\) 的第 \(2\times k\) 个状态即为 \(k\) 条不相交最长路径的长度和。
不过这些状态之间转移的关系错综复杂，并且对着方程仔细琢磨一下也好理解，于是这里就把所有的方程都列出来（这里 \(u\) 表示子树根节点，\(v\) 表示 \(u\) 的子结点，\(w\) 表示 \(u\) 与 \(v\) 之间边的边权）：
这些方程单独写出来固然清晰明白好理解，但是在敲代码的时候非常容易出错。因此 ICPC judge bruce merry 有一份非常巧妙的代码，使用一个双层循环来完成状态的转移，并且可以直接通过修改 \(E\) 的值来求出任意 \(k\) 条不相交最长路径。贴在这里：
static vector<int> recurse(vector<node> &nodes, int cur, int parent, int E) {node &n = nodes[cur];vector<int> dp(E + 1, 0);for (const auto &ch : n.edges) {if (ch.dest == parent) continue;auto sub = recurse(nodes, ch.dest, cur, E);for (int i = E-1; i >= 0; i--)for (int j = E - i; j >= 1; j--) {int score = dp[i] + sub[j] + ((j & 1) ? ch.len : 0);dp[i + j] = max(dp[i + j], score);}}return dp;
}最后输出二倍边权和减去除的路径总长即可求出答案。
完整代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
struct Node{int to,nxt,w;
}e[2*maxn];
int n,sum,ans;
int h[maxn],tot;
int f1[maxn],f2[maxn],f3[maxn],f4[maxn];
void Add(int u,int v,int w){tot++;e[tot].to=v;e[tot].nxt=h[u];e[tot].w=w;h[u]=tot;
}
void Dfs(int root,int fa){for(int i=h[root];i;i=e[i].nxt){int v=e[i].to;if(v==fa) continue;Dfs(v,root);f4[root]=max(f4[root],f3[root]+f1[v]+e[i].w);f4[root]=max(f4[root],f2[root]+f2[v]);f3[root]=max(f3[root],f2[root]+f1[v]+e[i].w);f4[root]=max(f4[root],f1[root]+f3[v]+e[i].w);f3[root]=max(f3[root],f1[root]+f2[v]);f2[root]=max(f2[root],f1[root]+f1[v]+e[i].w);f4[root]=max(f4[root],f4[v]);f3[root]=max(f3[root],f3[v]+e[i].w);f2[root]=max(f2[root],f2[v]);f1[root]=max(f1[root],f1[v]+e[i].w);}
}
int main(){scanf("%d",&n);for(int i=1;i<=n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);Add(a,b,c);Add(b,a,c);sum+=2*c;}Dfs(1,0);ans=f4[1];cout<<sum-ans;return 0;
}
注意事项
无向边开二倍数组。