[AGC005E] Sugigma: The Showdown

题意

传送门

思路

不会博弈

首先要是A能走到一条边 \((u,v)\) 满足 \(disb(u,v) \ge 3\) 那么A就可以在这俩个点之间伺机流窜，这个时候游戏无限。

在去掉这些边以后，A就无法跨越B所在的点了。因为剩下的情况中B都可以一步走到。也就是说，B会向某一个子树的叶节点不断逼近，那么A能做的，就是尽量走到离 \(S_b\) 最远的且能到达的（\(disa(S_a,x) ）那个叶节点，等着B结束游戏

那么只要用dfs搜索一遍就好了，碰见无限边就输出 \(-1\) 即可

#include 
const int N=200005;
int edge,Next[N<<1],to[N<<1],last[N],f[N],dep[N],ans,tag[N],n,s,t,x,y;
std::vector e[N];
void add(int x,int y){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
}
void dfs(int x,int y){
	f[x]=y;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (u==y) continue;
		dep[u]=dep[x]+1;
		dfs(u,x);
	}
}
bool chk(int x,int y){
	if (dep[x]=dep[x]) return;
	if (tag[x]){
		puts("-1");
		exit(0);
	}
	ans=std::max(ans,dep[x]);
	for (auto u:e[x]){
		if (u==y) continue;
		dfs2(u,x,deep+1);
	}
}
int main(){
	scanf("%d%d%d",&n,&s,&t);
	if (s==t){
		puts("0");
		return 0;
	}
	for (int i=1;i