CF1375G-Tree Modification

CF1375G-Tree Modification

题意

给定一棵有 $n$ 个结点的树，每次操作选取 3 个点 $i,j,k$ 满足 $i,j$ 存在连边，$j,k$ 存在连边，定义一次操作为：

1. 将 $i$ 的所有出边删除。
2. 将原先除去 $j$ 外与 $i$ 存在连边的点与 $k$ 连边。
3. 连接 $i,k$ 两点。

求最小的操作次数使得树存在度为 $n-1$ 的点。

Sol

考虑单次操作对树的影响，发现 $i$ 的深度 -1，$i$ 的子树内所有点的深度 -2。

那么考虑对于所有深度模 2 的意义下，相当于对树进行黑白染色。每次操作将改变一个点的颜色，而我们所求的最终状态为仅存在 1 个结点为白，其他结点全黑；或仅存在 1 个结点为黑，其他结点全白的树。

那么考虑 dfs 对树黑白染色，统计白点个数 $w$ 和黑点个数 $b$，答案即 $\min(w,b)-1$。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e6+1e1;
const lint INF=1e18+1e9;

struct Edge{
	int nxt,to;
}e[MAXN<<1];

bool vis[MAXN];
int head[MAXN],n,w,b,tot;

void Addedge(int u,int v){
	e[++tot]=(Edge){head[u],v};
	head[u]=tot;
	return;
}

void Dfs(int u,int dep){
	vis[u]=true,(dep^1 ? ++w : ++b);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!vis[v]) Dfs(v,dep^1);
	}
	return;
}

int main(void){

	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u=readint,v=readint;
		Addedge(u,v),Addedge(v,u);
	}
	Dfs(1,0);
	printf("%d\n",min(w,b)-1);

	return 0;
}