XYTREE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: chaty342
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

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