自动搬运

查看原文

来自洛谷，原作者为

	Mikefeng **

搬运于2025-08-24 22:52:31，当前版本为作者最后更新于2023-11-17 12:04:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：waauto 和 xzl 晚上 duel 这道题，于是晚上在床上想出了这道题。

题意

给定一些点，要把树分成几个连通块，每个连通块内要包含一个点，一个连通块的代价是边数乘 $2$ 减去关键点到最远的点的距离。问全局代价最小值。

做法

首先讲一下为什么局部代价是这样。

假设我们已经找到了一个连通块划分方案，如果一个人走完了要回到原点，那么代价是边数乘 $2$。

由于不需要回到原点，我们可以走到最深的叶子结点就停下，所以减去最远点距离。

同时这个贡献可以看做有一条链上每条边的贡献是 $1$，其余是 $2$。

考虑 dp，设 $f_{u,0/1,0/1}$ 表示目前节点是 $u$，所属关键点在子树内还是子树外，向父亲的边的贡献是 $1$ 还是 $2$。

然后就是大力分讨转移。

代码里有详细注释。

时间复杂度 $O(n)$，不是很懂为什么开 3s。

代码

const int N=5e5+5;
int n,k;
vector<int> e[N];
bool vis[N];
int f[N][2][2];
/*
向上或者向下 单边或者双边 
f[u][0][0]:向上的单边 
if(!vis[u]){
f[v][0][0]+1+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1])
}
else{
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1])
} 
f[u][0][1]:向上的双边 
if(!vis[u]){
f[v][0][1]+2+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1])
f[v][0][0]+1+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1]) 有一个可以是 f[other][1][0]+1 
}
else{
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1]) 有一个可以是 f[son][1][0]+1 
} 
f[u][1][0]:向下的单边 
if(!vis[u]){
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1]) 有一个可以是 f[son][1][0]+1
} 
else{
nope
}
f[u][1][1]:向下的双边 
if(!vis[u]){
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1])
} 
else{
nope
}
*/
inline void dfs(int u,int fa){
	for(int v:e[u]) if(v!=fa) dfs(v,u);
	if(vis[u]){
		for(int v:e[u]) if(v!=fa) f[u][0][0]+=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
		
		vector<int> g[2];
		F(i,0,1) g[i]=vector<int>(e[u].size()+1);
		F(i,0,int(e[u].size())-1){
			int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
			if(v!=fa){
				g[0][i+1]=g[0][i]+val;
				g[1][i+1]=min(g[1][i]+val,g[0][i]+min(val,f[v][1][0]+1));
			}else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
		}
		f[u][0][1]=g[1].back();
		
		f[u][1][0]=f[u][1][1]=1e9;
	}else{
		vector<int> g[4];
		F(i,0,1) g[i]=vector<int>(e[u].size()+1);
		g[1][0]=1e9;
		F(i,0,int(e[u].size())-1){
			int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
			if(v!=fa){
				g[0][i+1]=g[0][i]+val;
				g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][0]+1);
			}else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
		}
		f[u][0][0]=g[1].back();
		
		F(i,0,1) g[i]=vector<int>(e[u].size()+1);
		g[1][0]=1e9;
		F(i,0,int(e[u].size())-1){
			int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
			if(v!=fa){
				g[0][i+1]=g[0][i]+val;
				g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][1]+2);
			}else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
		}
		f[u][0][1]=g[1].back();
		
		F(i,0,3) g[i]=vector<int>(e[u].size()+1);
		g[1][0]=g[3][0]=1e9;
		F(i,0,int(e[u].size())-1){
			int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
			if(v!=fa){
				g[0][i+1]=g[0][i]+val;
				g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][0]+1);
				g[2][i+1]=min(g[2][i]+val,g[0][i]+min(val,f[v][1][0]+1));
				g[3][i+1]=min(g[3][i]+val,min(g[1][i]+min(val,f[v][1][0]+1),g[2][i]+f[v][0][0]+1));
			}else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i],g[2][i+1]=g[2][i],g[3][i+1]=g[3][i];
		}
		f[u][0][1]=min(f[u][0][1],g[3].back());
		
		F(i,0,1) g[i]=vector<int>(e[u].size()+1);
		F(i,0,int(e[u].size())-1){
			int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
			if(v!=fa){
				g[0][i+1]=g[0][i]+val;
				g[1][i+1]=min(g[1][i]+val,g[0][i]+min(val,f[v][1][0]+1));
			}else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
		}
		f[u][1][0]=g[1].back();
		
		for(int v:e[u]) if(v!=fa) f[u][1][1]+=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
	}
//	cout<<u<<' '<<f[u][0][0]<<' '<<f[u][0][1]<<' '<<f[u][1][0]<<' '<<f[u][1][1]<<'\n';
}
bool M2;
int main(){
	int Time=clock();
	look_memory;
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>k;
	F(i,1,k){
		int x;cin>>x;
		vis[x]=1;
	}
	F(i,1,n-1){
		int u,v;cin>>u>>v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfs(1,0);
	cout<<min(f[1][0][0],f[1][0][1])<<'\n';
	look_time;
	return 0;
}