自动搬运

查看原文

来自洛谷，原作者为

	beretty **

搬运于2025-08-24 21:56:27，当前版本为作者最后更新于2018-06-14 09:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

emm,一开始看这题感觉很难的样子

然后看了好久才看明白题意

看懂题意后其实做法其实并不难

就是先Dfs染一遍色

黑节点的儿子是白点，白点的儿子是黑点

然后用 f[i][j] 来表示i这个点为j方赢时最少控制的关键节点数

怎么求关键节点数目 ？

以黑方为例 ：

• 如果该点是白点，则只有其所有的儿子都是黑节点

• 如果该点是黑点，则只需要有一个儿子是黑点

最后再Dfs一遍把黑方白方的关键节点书都求出来，最后统计答案时就将黑白关键节点取个并集就好辣

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
const int M = 200005 ;
const int INF = 2147483646 ;
using namespace std ;
inline int read(){
	char c = getchar() ;int x=0,w=1;
	while(c>'9'||c<'0'){ if(c=='-') w=-1; c = getchar() ;}
	while(c>='0'&&c<='9'){ x = x*10+c-'0';c = getchar() ;}
	return x*w ;
}
struct E{
	int nex,to;
}edge[M<<1];
int hea[M] , num ;
inline void add_edge(int from,int to){
	edge[++num].nex = hea[from] ; 
	edge[num].to = to ;
	hea[from] = num ;
}
int n ;
int col[M] , f[M][2] ;
bool Control[M][2] , Son[M] ;
int MinAns = INF , Ansnum , Anstot ;

void Dye(int u){
	if(!Son[u]) f[u][0] = f[u][1] = 1 ;
	for(int i=hea[u];i;i=edge[i].nex){
		int v = edge[i].to ;
		col[v] = col[u]^1 ;
		Dye(v) ;
	}
}
void Dfs(int u,int j){
	if(j == col[u] && !f[u][j] ) f[u][j] = INF ; 
	for(int i=hea[u];i;i=edge[i].nex){
		int v = edge[i].to ;
		Dfs(v,j) ;
		if(j == col[u]) f[u][j] = min(f[u][j] , f[v][j]) ;
		else f[u][j] += f[v][j] ;
	}
}
void Ldfs(int u,int j){
	int tmp = INF ;
	for(int i=hea[u];i;i=edge[i].nex){
		int v = edge[i].to ;
		if(j==col[u]) tmp = min(tmp,f[v][j]) ;
		else Ldfs(v,j) ;
	}
	if(j==col[u]&&Son[u])
	  for(int i=hea[u];i;i=edge[i].nex){
	  	int v = edge[i].to ;
	  	if(f[v][j]==tmp)
	  	  Ldfs(v,j) ;
	  }
	if(!Son[u]) Control[u][j] = 1 ;
}
int main(){
	n = read() ;
	for(int i=2;i<=n;i++){
		int x = read();
		Son[x] = 1 ;
		add_edge(x,i) ;
	}
	col[1] = 1 ;
	Dye(1) ;
	Dfs(1,1) ; Dfs(1,0) ;
	Ldfs(1,1) ; Ldfs(1,0) ;
	for(int i=1;i<=n;i++)
	  if(Control[i][0]&Control[i][1]){
	  	MinAns = min(MinAns,i) ;
	  	Ansnum++ ;
	  	Anstot ^= i ;
	  }
	printf("%d %d %d\n",MinAns,Ansnum,Anstot) ;
	return 0;
}