#include <bits/stdc++.h>
using namespace std;
struct Node {
int sum, pmin;
Node(int s = 0, int pm = 0) : sum(s), pmin(pm) {}
};
Node mergeNode(const Node &a, const Node &b) {
Node c;
c.sum = a.sum + b.sum;
c.pmin = min(a.pmin, a.sum + b.pmin);
return c;
}
struct SegTree {
int n;
vector<Node> st;
void init(int n_) {
n = n_;
st.assign(4*n + 5, Node());
}
void update(int p, int l, int r, int idx, int val) {
if (l == r) {
st[p] = Node(val, min(0, val));
return;
}
int m = (l+r)/2;
if (idx <= m) update(p*2, l, m, idx, val);
else update(p*2+1, m+1, r, idx, val);
st[p] = mergeNode(st[p*2], st[p*2+1]);
}
};
static int Nglob;
static vector<vector<int>> G; // graf 0-based
static vector<int> val; // val[pos] = -1,0,+1, pos în [1..N]
static SegTree st;
int compute_danger() {
Node root = st.st[1];
if (root.pmin < 0) return 1;
if (root.sum != 0) return 1;
return 0;
}
void initialize(int N, const vector<int> &A, const vector<int> &B) {
Nglob = N;
G.assign(N, {});
for (int i = 0; i < N - 1; i++) {
int u = A[i];
int v = B[i];
G[u].push_back(v);
G[v].push_back(u);
}
st.init(Nglob);
val.assign(Nglob + 1, 0);
}
int cat(int X) {
int pos = X + 1;
val[pos] = +1;
st.update(1, 1, Nglob, pos, +1);
return compute_danger();
}
int dog(int X) {
int pos = X + 1;
val[pos] = -1;
st.update(1, 1, Nglob, pos, -1);
return compute_danger();
}
int neighbor(int X) {
for (int v : G[X]) {
int pos = v + 1;
val[pos] = -val[pos];
st.update(1, 1, Nglob, pos, val[pos]);
}
return compute_danger();
}
