自动搬运

查看原文

来自洛谷，原作者为

	ez_lcw **

搬运于2025-08-24 22:28:19，当前版本为作者最后更新于2021-01-17 17:10:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$O(n^2)$ 做法。

为了简化题目，如果以一个点为根的子树内不包含任何草莓节点，就把这棵子树去掉。

显然这样做不会影响答案，而且所有叶子节点都是草莓节点。

我们现在的问题变成了：对于这棵新树，有两个人同时从根开始去遍历它，然后问整棵树都被遍历完且两人最后回到根的最小时间是多少。

由于是时间，所以答案为两人走的路径长的 $\max$ 而不是和，没有什么显然的结论，所以考虑用 dp 来解决。

设 $dp(i,j)$ 表示遍历完以 $i$ 为根的子树，其中第一个人走了 $j$ 步，问第二个人最少走多少步。那么此时两人遍历完 $i$ 子树消耗的时间为 $\max(j,dp(i,j))$。

dp 转移明显可以用树形背包来解决，具体的 dp 方程和解释详见代码注释：

#include<bits/stdc++.h>

#define N 450
#define INF 0x7fffffff

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int n,k;
int cnt,head[N],nxt[N<<1],to[N<<1];
int fa[N],size[N],dp[N][N<<1];//遍历完i子树，第一个人走了j步，第二个人的最小步数 
bool vis[N];

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

bool dfs(int u)
{
	bool fruit=0;//fruit表示当前子树内有没有草莓
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa[u]||!v) continue;
		fa[v]=u;
		bool now=dfs(v);
		if(!now) to[i]=0;//如果v子树内没有草莓，我们就把to[i]设为0，表示v子树被删掉
		fruit|=now;
	}
	return fruit|vis[u];
}

void solve(int u)
{
	size[u]=1;
	dp[u][0]=0;
	for(int l=head[u];l;l=nxt[l])
	{
		int v=to[l];
		if(v==fa[u]||!v) continue;//如果v=0，说明v子树被删掉
		solve(v);
		size[u]+=size[v];
		for(int i=(size[u]-1)*2;i>=0;i--)//枚举第一个人走了i步，上界为整棵树的边数*2（每条边往返共两次），注意从大到小枚举
		{
			dp[u][i]=dp[u][i]+dp[v][0]+2;//这里是当第一个人不进入v子树时，此时第一个人不会走边(u,v)；同时这里利用了上一次的dp值进行更新
			if(i>=size[v]*2) dp[u][i]=min(dp[u][i],dp[u][i-size[v]*2]+dp[v][(size[v]-1)*2]);//这里是当第二个人不进入v子树时，此时第二个人不会走边(u,v)
			for(int j=min((size[v]-1)*2,i-2);j>=0;j--)//这里是第一个人和第二个人都进入v子树时，枚举第一个人进到v子树内走了多少步，顺序或倒序枚举都可以
				dp[u][i]=min(dp[u][i],dp[u][i-j-2]+dp[v][j]+2);//这里出现的“2”均是因为算上边(u,v)被往返走两次
		}
	}
}

int main()
{
	memset(dp,0x3f,sizeof(dp));
	n=read(),k=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		adde(u,v),adde(v,u);
	}
	for(int i=1;i<=k;i++)
		vis[read()]=1;
	dfs(1);
	solve(1);
	int ans=INF;
	for(int i=0;i<=(size[1]-1)*2;i++)
		ans=min(ans,max(i,dp[1][i]));
	printf("%d\n",ans);
	return 0;
}
/*
4 1
1 2
2 3
3 4
3
*/ 

关于时间复杂度的证明：dp 的实质可以看做枚举树中的点对 $(u,v)$，然后当且仅当存在某一个 $root$，使得 $u$ 和 $v$ 分别在 $root$ 的两个儿子的子树中。显然，对于每一个点对 $(u,v)$，有且仅有一个 $root=\operatorname{lca}(u,v)$。所以总时间复杂度是 $O(n^2)$。

其实学过树形背包的都不用看证明。

感谢神 Froggy 提供的思路。