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';
}
}
}