# XYTREE - Editorial

Author: chaty342
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093

2291

# PREREQUISITES:

Depth-first search

# PROBLEM:

You have a tree with N vertices, rooted at 1. Initially each vertex has A_i = 0.
Process Q queries on it:

• Type 1: given u,
• If u is a leaf set A_u = 1
• Otherwise set A_u to be the bitwise AND of all descendants of u.
• Type 2: count the number of good edges in the tree.
• An edge is good if the two components obtained on deleting it have the same bitwise AND.

# EXPLANATION:

For a node u, let p_u denote the parent of u.

Notice that under the given operation, if A_u = 0 then A_{p_u} = 0 will definitely hold, since we can only turn a 0 into a 1 and this can only done in a bottom-up fashion starting from the leaves.

Now letâ€™s analyze what a good edge looks like.
Letâ€™s remove the edge between u and p_u (of course, u \gt 1); let C_1 denote the subtree of u and C_2 denote the rest of the tree. Let x_1 and x_2 be their respective bitwise ANDs; weâ€™d like x_1 = x_2 to hold.

• If A_u = 0, then x_1 = 0. Our earlier observation tells us that A_{p_u} = 0, which means x_2 = 0 as well. So, this edge is definitely good.
• If A_u = 1, then every node in the subtree of u is 1, so x_1 = 1. For x_2 = 1 to hold, every vertex in the tree must then have a value of 1; equivalently, A_1 = 1 must hold.

So, we have the following conclusions:

• If A_1 = 1, then every edge is good
• Otherwise, the answer is the number of u \gt 1 such that A_u = 0.

All we need to do is maintain this information across updates.
Let ans denote the answer; initially ans = N-1 since every edge is good.

When we update a vertex u:

• If A_u doesnâ€™t change, then nothing changes.
• If A_u turns from 0 to 1, then the edge between u and p_u is no longer good so ans decreases by 1.

To quickly check this condition, note that we have the following observation:
A_u turns from 0 to 1 if and only if A_u = 0 and A_v = 1 for every child v of u.

Iterating across all the children of u for every update would take too much time, since we might do it multiple times for a given u.
Instead, letâ€™s do the reverse: whenever A_u changes to 1, we propagate that information to its parent p_u.

That is, letâ€™s keep an array ch, where ch_u denotes the number of children of u that are 0.
Initially, ch_u equals the number of children of u, which can be computed using a DFS.

Now, when updating a vertex u,

• If A_u = 1 or ch_u \neq 0, do nothing
• Otherwise, A_u changes from 0 to 1. When this happens, simply subtract 1 from ch_{p_u}, since p_u now has one less child that is 0.

This allows us to process each update in \mathcal{O}(1) time, leading to a solution in \mathcal{O}(N+Q) overall.

# TIME COMPLEXITY:

\mathcal{O}(N+Q) per testcase.

# CODE:

Setter's code (C++)
/* Author : Chaitanya Darwai */
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b,c)         for(int i=a; i<b; i+=c)
#define rrep(i,a,b)          for(int i=b-1; i>=a; i--)
#define vec                  vector
typedef vec<int>             vi;
typedef pair<int,int>        pii;
const int P = 1e9+7;
// const int P = 998244353;
const int N = 1e5+1;

void solve(int tcn){
int n;
cin >> n;

vec<vi> g(n);

for(int i = 0; i < n-1; ++i){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}

vi num(n), val(n, 0), par(n);

num[0] = g[0].size();
for(int i = 1; i < n; ++i){
num[i] = g[i].size()-1;
}

auto dfs = [&](int u, int _par, auto &dfs)->void{
par[u] = _par;
for(auto v : g[u]) if(v != _par) dfs(v, u, dfs);
};
dfs(0, -1, dfs);

int q;
cin >> q;

int ans = n-1;
while(q--){
int type;
cin >> type;

if(type == 2){
cout << ans << '\n';
}
else{
int u;
cin >> u;
--u;
if(!val[u] and !num[u]){
if(u) --num[par[u]];
val[u] = 1;
--ans;
}
if(!u and val[u]) ans = n-1;
}
}
}

signed main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

int test = 1;
cin >> test;
rep(i,0,test,1){
solve(i+1);
}
return 0;
}

Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
g[--u].push_back(--v);
g[v].push_back(u);
}

vector<int> par(n), unchanged(n), a(n);
auto dfs = [&] (const auto &self, int u, int p) -> void {
par[u] = p;
for (int v : g[u]) {
if (v == p) continue;
self(self, v, u);
++unchanged[u];
}
};
dfs(dfs, 0, 0);

int q; cin >> q;
int ans = n-1;
while (q--) {
int type; cin >> type;
if (type == 1) {
int u; cin >> u; --u;
if (a[u] == 0 and unchanged[u] == 0) {
a[u] = 1;
--ans;
if (u == 0) ans = n-1;
else --unchanged[par[u]];
}
}
else cout << ans << '\n';
}
}
}

1 Like

i cannot access the practice link for the problem

Can anyone please check why my code is giving WA ?? I used Euler Tour + Segment Tree to solve it & I donâ€™t find any mistake that I am doing. Here is the Code.
UPD: Got AC

could anyone please explain why my code is giving TLE?? code

Can anyone explain what is wrong in my code
Solution

Yet another case of Javaâ€™s io being slow, use PrintWriter and it gets AC (with a speedup of at least 0.5 seconds) submission

Havenâ€™t looked too deeply into the logic, but at the very least youâ€™re reading (or rather, interpreting) the input wrong.
The input edge a b doesnâ€™t mean that a is the parent of b, it just means that thereâ€™s an edge between them. You need to run a dfs to find parents.

Ah okay. Thanks