树上博弈,XY路径链以外的点有去无回,等于减掉当前自己所在子树后其他位置拱手相让。这么走有利当且仅当子树可走步数优于其他位置任意走法,否则走路径链。那么XY分别代入博弈,X第一步判断是否有利后,决定是否走路径链、走路径链的话Y第一步是否走路径链,以此类推。当XY相邻时,直接判断两者都走子树链,比较大小决定胜负。
因为这题修改单点删除的性质,维护减掉当前自己所在子树后其他位置任意走最大步数可以使用多重集维护区间max,不用线段树。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define deb(n) cout << #n << "=" << n << " "
#define debug(n) cout << #n << "=" << n << endl
#define div() cout << "_______________" << endl
const int N = 1e5 + 10, M = N * 2;
int n, stx, sty;
int h[N], e[M], ne[M], idx;
int from[N], save[N], maxd[N], L[N], R[N];
bool ste[N];
struct type {
int fa, pre, dis;
};
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int pre) {
for (int i = h[pre]; ~i; i = ne[i]) {
int to = e[i];
if (to == from[pre]) continue;
from[to] = pre;
dfs(to);
}
}
void oper() {
cin >> n >> stx >> sty;
for (int i = 0; i <= n + 1; i++) h[i] = -1, ste[i] = maxd[i] = L[i] = R[i] = 0; idx = 0;
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
from[stx] = -1;
dfs(stx);
int tmp = sty, cnt = 0;
while (~tmp) save[++cnt] = tmp, tmp = from[tmp];
reverse(save + 1, save + cnt + 1);
queue<type> q;
for (int i = 1; i <= cnt; i++) q.push({ save[i], save[i], 0 });
while (q.size()) {
int fa = q.front().fa, pre = q.front().pre, dis = q.front().dis; q.pop();
if (ste[pre]) continue;
ste[pre] = 1;
maxd[fa] = max(maxd[fa], dis);
for (int i = h[pre]; ~i; i = ne[i]) {
int to = e[i];
q.push({ fa, to, dis + 1 });
}
}
multiset<int> X, Y;
for (int i = 1; i < cnt; i++) {
int pre = save[i];
L[i] = max(L[i], i - 1 + maxd[pre]);
X.insert(i - 1 + maxd[pre]);
}
for (int i = cnt; i >= 2; i--) {
int pre = save[i];
R[i] = max(R[i], cnt - i + maxd[pre]);
Y.insert(cnt - i + maxd[pre]);
}
int l = 1, r = cnt;
for (int tt = 1; tt <= cnt; tt++) {
if (tt & 1) {
if (r - l == 1) {
if (l - 1 + maxd[save[l]] > cnt - r + maxd[save[r]]) cout << "1" << endl;
else cout << "0" << endl;
return;
}
if (L[l] > *Y.rbegin()) {
cout << "1" << endl;
return;
}
X.erase(X.find(l - 1 + maxd[save[l]]));
l++;
Y.erase(Y.find(cnt - l + maxd[save[l]]));
}
else {
if (r - l == 1) {
if (l - 1 + maxd[save[l]] <= cnt - r + maxd[save[r]]) cout << "0" << endl;
else cout << "1" << endl;
return;
}
if (R[r] >= *X.rbegin()) {
cout << "0" << endl;
return;
}
Y.erase(Y.find(cnt - r + maxd[save[r]]));
r--;
X.erase(X.find(r - 1 + maxd[save[r]]));
}
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; cin >> t;
while (t--) oper();
return 0;
}