这一题最重要的是设计状态。
首先，坏人不可能不被抓到，因为你再怎么说都可以一个一个抓，这样每一次逼到叶子节点。
一个显然的状态是 \(dp_{s,(a_1\sim a_m)}\) 代表警察在 \(s\)，坏人在 \(a_1\sim a_m\) 的最小时间，但是显然会爆掉。
- 性质一：因为坏人速度无限大，所以警察来抓他们的时候一定呆在叶子节点。
如果不在叶子节点，一定可以省去时间。
- 性质二：坏人在哪一个节点不重要，只和警察的相对位置重要。
这也是因为坏人的速度是无限大。
所以现在有另一个状态 \(dp_{u,(c_{1}\sim c_{sz})}\) 代表警察在 \(u\)，在 \(1\sim sz\) 个 \(u\) 的子树内分别有 \(c_1\sim c_{sz}\) 个坏人。但是还是会爆炸。
分析一下爆炸的本质。因为我们是模拟警察从一个节点到另一个节点，所以相对方位有很多种。但是其实因为坏人速度无限大，其实警察可以看作是从一个边到另一个边，因为坏人可以“预判”警察下一步是什么（可以想象为，警察在 \(u\rightarrow v\) 中间时定住了，\(u,v\) 两边的坏人分别可以随意交换顺序）。
因此设计状态：\(dp_{u,v,al,c}\) 表示目前警察 \(u\rightarrow v\) 这个方向，警察面向的子树内有 \(c\) 个坏人，现在一共还剩 \(al\) 个坏人。
考虑转移：枚举下一步，那么新的时间其实就是坏人的所有排列的下一步得到的最小时间。这个可以用一个背包求得。
代码很好写。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55;
int n,s,f[N][N][N][N],d[N][N],m,x[N],cnt,vis[N];
vector<int> e[N];
void dfs(int u,int fa){
cnt+=vis[u];
for (auto v : e[u]){
if (v^fa) dfs(v,u);
}
}
int sol(int u,int v,int al,int in){
auto &ans=f[u][v][al][in];
if (~ans) return ans;
if (!al) return ans=0;
if (e[v].size()==1) return ans=sol(v,u,al-in,al-in)+d[u][v];
int g[N];
g[0]=1e9;
for (int i=1; i<=al; i++) g[i]=-1e9;
for (auto p : e[v]){
if (p^u){
for (int i=in; i; i--){
for (int j=1; j<=i; j++){
g[i]=max(g[i],min(g[i-j],sol(v,p,al,j)+d[u][v]));
}
}
}
}
return ans=g[in];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<n; i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back(v);
e[v].push_back(u);
d[u][v]=d[v][u]=w;
}
cin>>s>>m;
for (int i=1; i<=m; i++){
cin>>x[i];
vis[x[i]]++;
}
memset(f,-1,sizeof f);
int ans=1e9;
for (auto u : e[s]){
cnt=0;
dfs(u,s);
ans=min(ans,sol(s,u,m,cnt));
}
cout<<ans<<"\n";
return 0;
}