In this HackerEarth A game of trees problem solution You are given a rooted tree with n vertices. Here, A and B are playing with the tree. In each turn (starting with A), each player can select a vertex that contains no parent and delete a path with at least two vertices starting from v.
A player loses if he or she cannot make the turn in the game. For each test case, determine who will win.
HackerEarth A game of trees problem solution.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e5+100, M=18;
vector<int> g[N];
struct dat{
int forced, sz;
vector<int> cnt, val, to[2];
int add_node(int v){
to[0].push_back(-1);
to[1].push_back(-1);
cnt.push_back(0);
val.push_back(v);
return sz ++;
}
dat(){
forced = sz = 0;
add_node(0);
}
int get_mex(){
assert(cnt[0] < (1 << M));
int ret=0, it=0;
for(int bt=M-1 ; bt>=0 ; bt--){
bool fhv = (forced & (1 << bt));
auto go = [&](bool f) -> int{
int nxt = to[f][it];
if(nxt == -1)
return (((ret << 1) | f) << bt) | (((1 << bt)-1) & forced);
if(cnt[nxt] < (1 << bt)){
it = nxt;
ret = (ret << 1) | f;
return -1;
}
return -2;
};
int cur = go(fhv);
if(cur>=0)
return cur^forced;
if(cur == -1)
continue;
cur = go(!fhv);
if(cur>=0)
return cur^forced;
}
return ret;
}
void add(int x){
x ^= forced;
int it=0, v=0;
vector<int> path = {it};
bool change = false;
for(int bt=M-1 ; bt>=0 ; bt--){
bool hv = (x & (1 << bt));
v <<= 1;
v |= hv;
if(to[hv][it] == -1){
to[hv][it] = add_node(v);
change = true;
}
cnt[it] ++;
it = to[hv][it];
path.push_back(it);
}
cnt[it] ++;
if(!change)
for(auto ver : path)
cnt[ver] --;
}
bool merge(dat *other){
if(sz < other->sz)
return false;
for(int i=1 ; i<other->sz ; i++)
if(other->to[0][i] == -1 && other->to[1][i] == -1)
add(other->val[i] ^ other->forced);
return true;
}
void force(int x){
forced ^= x;
}
};
pair<dat*, int> dfs(int v, int par){
dat *ret = new dat();
int ch=0;
vector<pair<dat*, int> > vec;
for(auto u : g[v]){
if(u == par)
continue;
auto child = dfs(u, v);
auto cur = child.first;
int cmex = cur->get_mex();
ch ^= cmex;
cur->add(child.second);
vec.push_back({cur, cmex});
}
for(auto U : vec){
auto u = U.first;
auto cmex = U.second;
u->force(ch ^ cmex);
if(!ret->merge(u)){
u->merge(ret);
ret = u;
}
}
return {ret, ch};
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;cin >> t;
while(t --){
int n;cin >> n;
for(int i=0 ; i<n ; i++)
g[i].clear();
for(int i=1 ; i<n ; i++){
int p;cin >> p;p --;
g[i].push_back(p);
g[p].push_back(i);
}
cout << (dfs(0, -1).first->get_mex() ? "A" : "B") << "n";
}
}
Second solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 14, maxd = 16;
struct Trie {
int lazy;
vector<array<int, 2> > t;
vector<int> cnt;
Trie() : lazy(0), t(1), cnt(1) {}
void add(int x, bool final = false) {
if (!final)
x ^= lazy;
int p = 0;
for (int b = maxd - 1; b >= 0; b--) {
int dir = x >> b & 1;
if (!t[p][dir])
if (!final) {
add(x, true);
return;
}
else {
t[p][dir] = t.size();
t.push_back({});
cnt.push_back(0);
}
p = t[p][dir];
cnt[p] += final;
}
}
int mex() {
int p = 0, ans = 0;
for (int b = maxd - 1; b >= 0; b--) {
int dir = lazy >> b & 1;
if (!t[p][dir])
return ans;
else if (cnt[t[p][dir]] < 1 << b)
p = t[p][dir];
else {
ans |= 1 << b;
if (!t[p][!dir])
return ans;
p = t[p][!dir];
}
}
assert(false);
}
void dfs(vector<int> &elements, int v = 0, int val = 0, int h = maxd) {
if (h == 0) {
elements.push_back(val ^ lazy);
return;
}
if (t[v][0])
dfs(elements, t[v][0], val, h - 1);
if (t[v][1])
dfs(elements, t[v][1], val | 1 << h - 1, h - 1);
}
vector<int> get_elements() {
vector<int> elements;
dfs(elements);
return elements;
}
Trie &operator+=(Trie &o) {
if(o.t.size() > t.size())
swap(*this, o);
for (auto x : o.get_elements())
add(x);
return *this;
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> g[n];
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
p--;
g[p].push_back(i);
}
Trie sack[n];
int grundy[n];
for (int v = n - 1; v >= 0; v--) {
int child_grundy = 0;
for(auto child : g[v])
child_grundy ^= grundy[child];
for(auto child : g[v]){
sack[child].lazy ^= child_grundy ^ grundy[child];
sack[v] += sack[child];
}
grundy[v] = sack[v].mex();
sack[v].add(child_grundy);
}
cout << (grundy[0] ? "An" : "Bn");
}
}