题意：
在一棵树上，有一个警察和$m$个罪犯。边有长度。警察的速度为1，罪犯的速度可以任意快。如果双方都按最优策略行动，且每一时刻每个人都知道所有人的位置。当罪犯和警察相遇时他就被抓住了。求警察最快多久可以抓住所有罪犯。
题解：
一开始在想双方的最优策略是什么，但除了小偷每次跑到叶子坐以待毙以外并没有想到什么。遂膜之。
设$f_{i, j, k}$表示警察开始走第$i$条边，当前总共有$j$个罪犯没被抓，警察前面有$k$个罪犯。
- 如果$i$连向的是一个叶子，那么叶子上所有$k$个罪犯都会被抓，$f_{i, j, k} = f_{i \oplus 1, j - k, j - k} + w_i$；
- 如果$i$连向的不是叶子，那么$f_{i, j, k} = \min\{f_{l, j, a_l}\} + w_i$，其中$l$为$i$的后继边，$a_l$为$l$里面有多少罪犯。因为罪犯按最优策略行动，所以他们要让$\min\{f_{l, j, a_l}\}$最大。所以就要通过把$k$恰当地分配给所有$l$，这个做个背包就好了。复杂度看上去是$O(n^6)$的，但很玄学地跑得很快。可能真正的复杂度是很小的吧。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int A = 50 * 50 * 50;
int n, num = 1, fst[60], deg[60], s, m, cnt[60], f[110][60][60]; // 在第i条边，总共有j个罪犯，前面有k个罪犯
int sum[60];
struct edge
{
int x, y, c, n;
} e[110];
void ins(int x, int y, int c)
{
e[++num] = {x, y, c, fst[x]};
fst[x] = num;
}
void dfs(int x, int fa)
{
sum[x] = cnt[x];
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (y == fa) continue;
dfs(y, x);
sum[x] += sum[y];
}
}
int F(int i, int j, int k)
{
if (f[i][j][k] < 0x3f3f3f3f || k == 0) return f[i][j][k];
int y = e[i].y;
if (deg[y] == 1)
{
f[i][j][k] = F(i ^ 1, j - k, j - k) + e[i].c;
}
else
{
int g[60];
memset(g, 0, sizeof(g));
g[0] = 0x3f3f3f3f;
for (int l = fst[y]; l; l = e[l].n)
{
if (l == (i ^ 1)) continue;
for (int o = k; o > 0; o--)
for (int p = 1; p <= o; p++)
g[o] = max(g[o], min(g[o - p], F(l, j, p)));
}
f[i][j][k] = g[k] + e[i].c;
}
// printf("%d %d %d %d %d\n", e[i].x, e[i].y, j, k, f[i][j][k]);
return f[i][j][k];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
ins(x, y, c);
ins(y, x, c);
deg[x]++;
deg[y]++;
}
scanf("%d%d", &s, &m);
for (int i = 1; i <= m; i++)
{
int x;
scanf("%d", &x);
cnt[x]++;
}
dfs(s, 0);
memset(f, 63, sizeof(f));
for (int i = 2; i <= num; i++)
f[i][0][0] = 0;
int ans = 0x3f3f3f3f;
for (int i = fst[s]; i; i = e[i].n)
ans = min(ans, F(i, m, sum[e[i].y]));
printf("%d\n", ans);
}