0%

「AtCoder Grand Contest」「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)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}