「AGC005E」Sugigma: The Showdown

AGC005E - Sugigma: The Showdown

题意

有 \(n\) 个点，\(n-1\) 条红边和 \(n-1\) 条蓝边分别把这些点连成一棵树

一开始第一个人在 \(x\)，第二个人在 \(y\)，第一个人先手，轮流操作

第一个人走红边，第二个人走蓝边，每次操作可以不动或走一条边。

当两个人相遇的时候游戏结束，第一个人希望最大化总步数，第二个人希望最小化，两个人绝顶聪明

问游戏能否结束，如果可以结束输出最后的步数

做法

考虑如果有一条红边两个端点在蓝树上的距离 \(>2\)，那么第一个人只要走过了一次这条边，第二个人就不可能结束游戏

考虑以 \(y\) 为根构建蓝树，第一个人的移动视作在这棵树上跳，如果走的红边两个端点在蓝树上的距离 \(\le 2\)，那么不可能跳出以第二个人所在点为根的子树

我们只要以 \(x\) 为起点开始搜索，如果一个点被第一个人走到的时间小于第二个人走到的时间，这个点才可以继续，否则第一个人会在这里死掉

判掉游戏不会结束的情况，第一个人只能在可以到达的点中找一个离 \(y\) 最远的等死

判距离是否 \(>2\) 可以深度和父子关系搞搞，也可以直接求距离，复杂度 \(\mathcal O(n)\) 或 \(\mathcal O(n\log n)\)

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 200005;
int n, x, y, ans, top[N], dep[N], fa[N], siz[N], d[N];
bool vis[N];
vector<int> a[N], b[N];
void dfs1(int u){
	siz[u]=1;
	for(int v:b[u]) if(v!=fa[u]) dep[v]=dep[u]+1, fa[v]=u, dfs1(v), siz[u]+=siz[v];
}
void dfs2(int u){
	int son=0;
	for(int v:b[u]) if(v!=fa[u] && siz[v]>siz[son]) son=v;
	if(son) top[son]=top[u], dfs2(son);
	for(int v:b[u]) if(v!=fa[u] && v!=son) top[v]=v, dfs2(v);
}
void dfs3(int u, int fa=0){
	if(vis[u] && d[u]<dep[u]){
		puts("-1");
		exit(0);
	}
	if(d[u]>=dep[u]) return;
	ans=max(ans, dep[u]);
	for(int v:a[u]) if(v!=fa) d[v]=d[u]+1, dfs3(v, u);
}
inline int dis(int x, int y){
	int ans=dep[x]+dep[y];
	while(top[x]!=top[y]) if(dep[top[x]]<dep[top[y]]) y=fa[top[y]]; else x=fa[top[x]];
	return ans-min(dep[x], dep[y])*2;
}
int main() {
	read(n), read(x), read(y);
	for(int i=1, u, v; i<n; ++i) read(u), read(v), a[u].push_back(v), a[v].push_back(u);
	for(int i=1, u, v; i<n; ++i) read(u), read(v), b[u].push_back(v), b[v].push_back(u);
	dfs1(y), top[y]=y, dfs2(y);
	for(int i=1; i<=n; ++i) for(int j:a[i]) if(i<j)
		if(dis(i, j)>2) vis[i]=vis[j]=1;
	dfs3(x);
	return printf("%d", ans<<1), 0;
}