题解 [SEERC2019]Game on a Tree

这题感觉好神仙,还是没有自己独立想出来。

题目链接

题目分析

如果 \(u,v\) 是祖先关系,那么我们就给 \(u,v\) 连上一条双向边,现在问题就变成了:给定一张无向图, Alice 选择从某处开始放一个棋子,然后 Bob 和 Alice 依次移动这个棋子,但是不能走到到过的地方,无法操作者败。

结论就是:如果有完美匹配,那么 Bob 胜,否则 Alice 胜。


结论证明:

一、有完美匹配。

此时 Bob 只需要根据 Alice 走到的位置,然后走它在完美匹配中匹配到的点即可,这样最终 Alice 会无路可走。

二、没有完美匹配。

不妨设最大匹配为 \((a_1,a_2),(a_3,a_4),\dots\) ,那么假如 Alice 从一个没有在最大匹配中的点开始,那么 Bob 显然不可能再走到一个没有在最大匹配中的点,否则就形成了一条增广路,所以 Alice 就用“有完美匹配”中 Bob 的策略即可胜利。


由于是题目给的是一棵树,所以很好求最大匹配,设 \(dp_u\) 表示 \(u\) 这棵子树中最少有多少点没有匹配到即可。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005;
struct Edge{
	int v,nt;
	Edge(int v=0,int nt=0):
		v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
	e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dp[maxn];
void dfs(int u,int fa){
	dp[u]=-1;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);dp[u]+=dp[v];
	}
	dp[u]=(dp[u]<0?-dp[u]:dp[u]);
}
int main(){
	int n;read(n);
	for(int i=1;i<n;++i){
		int u,v;
		read(u),read(v);
		qwq(u,v);qwq(v,u);
	}
	dfs(1,0);
	puts(dp[1]?"Alice":"Bob");
	return 0;
}

上一篇:【LOJ#536】「LibreOJ Round #6」花札


下一篇:安全测试(xss \ csrf 攻击)