【Codeforces 868E】Policeman and a Tree
树形DP。
题目大意：
给定一棵树，带点权。有一个警察，一开始在 $s$ 点，每秒只能移动一格。有 $m$ 个小偷分布在树上，速度无穷大。警察和小偷在同一位置时，小偷会被抓住。假设警察和小偷足够聪明，求抓住所有小偷的最短时间。
题解：
首先肯定有解，因为每次只盯牢一个的话，把他逼到叶子上就抓住了。
考虑树形DP。
令 $f[u][v][x][y]$ 表示当前在 $v$，是从 $u$ 走过来的，$v$ 关于 $u$ 的子树里有 $x$ 个小偷，另外位置有 $y$ 个小偷，抓完所有小偷的方案数。
当 $v$ 是叶子的时候，$f[u][v][x][y]=f[v][u][y][0]+[y=0]\times \mathrm{dist}(u,v)$，表示逼死了这 $x$ 个，如果剩下还有那么回头抓剩下的。
对任意 $u,v$，有 $f[u][v][0][0]=0$。
对于剩下的情况，小偷会分布在 $x$ 的子树中。由于小偷和警察是足够聪明的，对每种小偷的分布情况，警察会选择最优方案。那么小偷要做的就是使警察的最优方案尽可能大。
我们令 $g[x]$ 表示当前处理了一些子树，共分配了 $x$ 个小偷时，能使警察的最优方案需要花费的最劣时间。
则枚举 $v$ 的子树 $t$（$t\neq u$），再枚举分配的小偷个数。则：
这里 $\min$ 表示警察使自己的方案尽可能优，$\max$ 表示小偷使警察的方案尽可能劣。
最后 $f[u][v][x][y]=g[x]$，是最优决策。
求 $f$ 的时候使用记忆化搜索即可。
状态总数为 $n^3$，每次转移 $O(n^2)$，所以时间复杂度 $O(n^5)$，远远跑不满，可以通过。
Code：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=52;
int f[N][N][N][N],sz[N],n,m,head[N],cnt,s,deg[N];
struct edge{
int to,nxt,w;
}e[N<<1];
void dfs(int now,int pre){
for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre)dfs(e[i].to,now),sz[now]+=sz[e[i].to];
}
int dp(int u,int v,int x,int y){
int&F=f[u][v][x][y];
if(F!=-1)return F;
if(x==0&&y==0)return F=0;
if(deg[v]==1)return F=dp(v,u,y,0)+(y?e[head[v]].w:0);
int g[N];
memset(g,0,sizeof g);
g[0]=0x3fffffff;
for(int i=head[v];i;i=e[i].nxt)
if(e[i].to!=u){
for(int s=x;s;--s)
for(int t=s;t;--t)
g[s]=max(g[s],min(g[s-t],dp(v,e[i].to,t,x+y-t)+e[i].w));
}
return F=g[x];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v,w;
cin>>u>>v>>w;++deg[u],++deg[v];
e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
}
cin>>s>>m;
for(int x;m--;)
cin>>x,++sz[x];
memset(f,-1,sizeof f);
dfs(s,0);
int ans=2e9;
for(int i=head[s];i;i=e[i].nxt)
ans=min(ans,dp(s,e[i].to,sz[e[i].to],sz[s]-sz[e[i].to])+e[i].w);
cout<<ans<<'\n';
return 0;
}