PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Euler tour of a tree, segment trees with lazy propagation
PROBLEM:
You’re given a tree on N vertices, with each edge having a value.
Let f(u, v) denote the XOR-sum of edges on the path from u to v.
Process Q updates/queries on the tree:
- Given u and X, XOR the value of every edge in the subtree of u by X.
- Given u, compute the sum of f(x, y) across all pairs of vertices lying in the subtree of u.
EXPLANATION:
Let’s forget the updates for now, and pretend we only have queries.
That is, with the edge weights fixed, we want to answer the following for a fixed vertex u:
- Compute the sum of the XOR-sums of all path weights across all paths lying in the subtree of u.
To solve this, first we must make a small reduction.
Let’s define P_v to be the XOR-sum of all edge weights on the path from the root to v.
With this definition, observe that the XOR-sum of some path (x, y) simply equals P_x \oplus P_y, i.e. f(x, y) = P_x \oplus P_y.
This is because P_x\oplus P_y will include every edge on the path from x to y exactly once, and every edge from the root to \text{lca}(x, y) exactly twice; however XOR-ing the same value twice cancels it out, so the resulting value is just the XOR-sum of all edges on the (x, y) path.
Thus, after computing the values P_x for all x, to answer a query u we just want to know the sum of the pairwise XORs of all values of P lying in the subtree of u.
To make this even easier to work with, note that after building the Euler tour of the tree, each subtree corresponds to some subarray; so we’re really just querying for the sum of pairwise XORs of some subarray.
So, we can now focus on just solving this problem for subarrays of an array.
We now work entirely with arrays.
Suppose we have an array A, and we want to answer queries of the form (L, R), each asking for
Addition and XOR-sum don’t really work well with each other, so this is a bit hard to do directly.
Instead, since we’re working with a bitwise operation, we work with each bit individually, and add up the contributions of each one.
That is, if we define ct_b to be the number of pairs (i, j) such that A_i \oplus A_j has the bit b set, then the value of the above summation will be
Computing ct_b is not too hard: note that A_i\oplus A_j will have bit b set if and only if exactly one of A_i and A_j has b set and the other one has it unset.
So, if there are x_b elements that have b set, and y_b elements that have it unset, we simply have ct_b = x_b\cdot y_b.
Given that we’re working with a fixed array A, computing x_b and y_b quickly is trivial: just build a prefix sum array corresponding to the bit b, for example.
So, for any single bit, it’s possible to obtain the contribution in constant time with linear contribution.
If A_{\max} denotes the maximum element of the array, we only need to care about the smallest \log A_{\max} bits.
So, precomputation for each bit will take \mathcal{O}(N\cdot \log A_{\max}) time, and then answering a query takes \mathcal{O}(\log A_{\max}) time.
Since we’re working with values \le 10^6, we have \log A_{\max} \le 20 meaning this is very fast.
To summarize, answering only queries is fairly easy: build the Euler tour of the tree to transform subtree queries into subarray queries; and then each query can be answered by adding up the contribution of each bit, which only requires knowing how many elements in the range have the bit set/unset.
Next, we need to extend this to work with updates.
So, suppose we have the update (u, X), meaning that all edge weights in the subtree of X are XOR-ed by X.
Recall that we only care about the values P_v, denoting the XOR of weights on the 1\to v path.
Let’s analyze how these values change.
Consider some vertex v in the subtree of u.
Suppose there are k edges connecting u and v.
Each of these k edges will have its value XOR-ed by X.
So, P_v will become P_v \oplus \underbrace{\left(X \oplus X \oplus \ldots\oplus X\right)}_{k \text{ times}}
In particular, if k is even then P_v doesn’t change at all, while if k is odd then P_v just becomes P_v \oplus X.
So, in terms of updating the values of P: all vertices at even distance from u see no change, while all vertices at odd distance from u have their value XOR-ed by X.
Recall that to answer queries, we considered each bit independently.
So, once again let’s look at a single bit b, and see what the change is there.
Note that we now have a boolean sequence.
- If X doesn’t have b set, then there’s no change at all to anything in the subtree (with respect to b).
- If X does have b set, then all vertices in the subtree at odd distance from u must be XOR-ed by 1.
This is equivalent to just flipping them from 0 to 1 and vice versa.
We need to process this while also being able to return the count of zeros/ones in some range to answer queries.
So, we need a data structure that maintains a boolean sequence while supporting the following:
- Given a range, return the counts of zeros/ones in the range.
Note that since the sequence is boolean, the count of ones is just the sum of the range; and the count of zeros can be inferred from the length and the count of ones.
So, it’s enough to be able to find the sum of the range. - Given a range, flip all elements that correspond to vertices with a certain depth parity (whichever is the opposite of the depth of u).
If we didn’t have the parity condition on flips, this can be easily handled by a lazy segment tree: flipping entire ranges can be done by maintaining a lazy flag, and its effect on the sum of a node is also easily found.
To account for the parity condition as well: note that the depth parity of nodes doesn’t change at all.
So, we can must maintain two separate segment trees: one corresponding to even-depth vertices and one corresponding to odd-depth vertices.
Now, a subtree update can be done on only one of the trees; and will correspond to an entire range.
Answering queries needs to be done by querying both trees, though that’s just a constant-factor increase.
TIME COMPLEXITY:
\mathcal{O}((N + Q\log N)\log{10^6}) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Node {
using T = int;
T unit = 0;
T f(T a, T b) { return a+b; }
Node *l = 0, *r = 0;
int lo, hi;
bool mflip = false;
T val = unit;
Node(int _lo,int _hi):lo(_lo),hi(_hi){}
T query(int L, int R) {
if (R <= lo || hi <= L) return unit;
if (L <= lo && hi <= R) return val;
push();
return f(l->query(L, R), r->query(L, R));
}
void flip(int L, int R) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
val = hi-lo - val;
mflip ^= 1;
}
else {
push(), l->flip(L, R), r->flip(L, R);
val = f(l->val, r->val);
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mflip)
l->flip(lo,hi), r->flip(lo,hi), mflip = 0;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector adj(n, vector<array<int, 2>>());
for (int i = 0; i < n-1; ++i) {
int u, v, w; cin >> u >> v >> w;
adj[--u].push_back({--v, w});
adj[v].push_back({u, w});
}
int q; cin >> q;
vector<array<int, 3>> queries(q);
for (auto &[x, y, z] : queries) {
cin >> x >> y;
--y;
if (x == 1) cin >> z;
}
vector in(n, 0), out(n, 0), dep(n, 0), val(n, 0), subsz(n, 1);
vector chin(n, -1), chout(n, -1);
vector<int> evens, odds;
auto dfs = [&] (const auto &self, int u, int p) -> void {
if (dep[u] == 0) {
in[u] = evens.size();
evens.push_back(u);
}
else {
in[u] = odds.size();
odds.push_back(u);
}
for (auto [v, w] : adj[u]) {
if (v != p) {
dep[v] = dep[u] ^ 1;
val[v] = val[u] ^ w;
self(self, v, u);
subsz[u] += subsz[v];
if (chin[u] == -1) chin[u] = in[v];
chout[u] = out[v];
}
}
if (dep[u] == 0) {
out[u] = evens.size();
}
else {
out[u] = odds.size();
}
};
dfs(dfs, 0, 0);
vector ans(q, 0ll);
int sze = size(evens), szo = size(odds);
Node *seg_even = new Node(0, sze), *seg_odd = new Node(0, szo);
for (int bit = 0; bit < 20; ++bit) {
seg_even = new Node(0, sze);
seg_odd = new Node(0, szo);
for (int i = 1; i < n; ++i) {
if ((val[i] >> bit) & 1) {
if (dep[i] == 0) seg_even -> flip(in[i], in[i]+1);
else seg_odd -> flip(in[i], in[i]+1);
}
}
for (int i = 0; i < q; ++i) {
auto &[x, u, z] = queries[i];
if (x == 1) {
int b = (z >> bit) & 1;
if (b == 1 and chin[u] != -1) {
if (dep[u] == 0) {
seg_odd -> flip(chin[u], chout[u]);
}
else {
seg_even -> flip(chin[u], chout[u]);
}
}
}
else {
int tot = subsz[u];
int ct = 0;
if (dep[u] == 0) {
ct = seg_even -> query(in[u], out[u]);
if (chin[u] != -1) ct += seg_odd -> query(chin[u], chout[u]);
}
else {
ct = seg_odd -> query(in[u], out[u]);
if (chin[u] != -1) ct += seg_even -> query(chin[u], chout[u]);
}
ans[i] += (1ll << bit) * ct * (tot - ct);
}
}
}
for (int i = 0; i < q; ++i) {
if (queries[i][0] == 2) cout << ans[i] << '\n';
}
}
}