CF868E

Daily problem.

感觉是一个易懂的方法。

首先手玩样例，发现罪犯可以在警察进入一棵子树时从警察后面溜走，所以警察很有可能要重复走某些路径，这样用树形 dp 比较困难，所以可以考虑更像放在序列上的 dp。

设 $dp_{u,t}$ 为当前在 $u$ 位置，还有 $t$ 个罪犯没抓到，最快多久全抓到。首先限制 $u$ 为叶子，则这个状态是没有后效性的，因为如果上一步警察移动到 $u$，则所有剩下的罪犯都可以随便移动。并且罪犯在最优策略下一定是移动到叶子，故得证。

然后考虑转移。转移时，罪犯要分配每个叶子上去多少人，所以另外设一个 dp 状态 $f_{v,i}$ 表示 $[1,v]$ 的点内分配了 $i$ 个罪犯，警察在最优决策下，最慢多久抓到全部罪犯。以此辅助转移。类似背包转移：$f_{v,i}=\max(f_{v-1,i},\max_{j\le i}\min(f_{v-1,i-j},dis_{u,v}+dp_{v,t-j}))$。

最后还要看警察一开始从 $s$ 先去到哪个叶子，与上面类似地转移即可。

时间复杂度 $O(n^5)$。跑了 100ms-。而且看其他题解，显然可以至少优化到 $O(n^4\log n)$，把背包部分换成一个二分即可。不过应该也快不了多少。😃

code：

int n,m,s,c[N],id[N],deg[N],dis[N][N],dp[N][N],f[N][N];
vector<int> g[N];
int tot,head[N];
struct node{int to,nxt,cw;}e[N<<1];
il void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
void getDis(int u,int f,int s,int w=0){
	dis[s][u]=dis[s][f]+w;
	go(i,u){
		int v=e[i].to;
		if(v==f)continue;
		getDis(v,u,s,e[i].cw);
	}
}
void dfs(int u,int f,int s){
	if(!g[s].size())g[s].eb(0);
	g[id[u]=s].eb(u);
	go(i,u){
		int v=e[i].to;
		if(v==f)continue;
		dfs(v,u,s);
	}
}
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n-1){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
		deg[u]++,deg[v]++;
	}
	scanf("%d%d",&s,&m);
	int p=0;
	go(i,s)dfs(e[i].to,s,++p);
	rep(i,1,m){
		int x;scanf("%d",&x);
		c[id[x]]++;
	}
	rep(u,1,n)getDis(u,0,u);
	rep(u,1,n)dp[u][0]=0;
	rep(t,1,m){
		rep(u,1,n){
			mems(f,-0x3f);
			f[0][0]=inf;
			rep(v,1,n){
				rep(i,0,t)f[v][i]=f[v-1][i];
				if(deg[v]>1)continue;
				rep(j,1,t)rep(i,j,t){
					f[v][i]=max(f[v][i],min(f[v-1][i-j],dis[u][v]+dp[v][t-j]));
				}
			}
			dp[u][t]=f[n][t];
		}
	}
	int ans=inf;
	rep(k,1,p){
		mems(f,-0x3f);
		f[0][0]=inf;
		int sz=(int)g[k].size()-1;
		rep(u,1,sz){
			rep(i,0,c[k])f[u][i]=f[u-1][i];
			if(deg[g[k][u]]>1)continue;
			rep(j,1,c[k])rep(i,j,c[k]){
				f[u][i]=max(f[u][i],min(f[u-1][i-j],dis[s][g[k][u]]+dp[g[k][u]][m-j]));
			}
		}
		ans=min(ans,f[sz][c[k]]);
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}