PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy-Med
PREREQUISITES:
Tree data structures (or dynamic connectivity)
PROBLEM:
You’re given a tree on N vertices, with weights on edges. f(x, y) denotes the bitwise OR of the weights on the edges of the path from x to y.
Process Q updates, each of which changes the weight of one edge. After each update, compute the sum
EXPLANATION:
Let’s solve a restricted version of the problem first: suppose all weights (initial and updates) are either 0 or 1.
Now, f(x, y) simply means “does there exist an edge with weight 1 on the path from x to y?”
This is equal to the total number of paths, minus the number of paths that don’t contain any ones on them.
Let’s pretend that each edge with weight 1 is deleted from the tree, so we’re left with a forest, say with component sizes s_1, s_2, \ldots, s_k.
Every pair of vertices within a component will not have a 1 on the path between them, while every pair of vertices in different components will.
So, the quantity we’re looking for is exactly
Under this model, point updates to edges correspond to essentially deleting/adding them, and hence the component sizes (and counts) changing.
There are standard techniques that can deal with this: offline dynamic connectivity and link-cut trees, for two.
There are also more “ad-hoc” approaches using more common algorithms: for example, here’s one.
Let’s root the tree at vertex 1, and define c_u to be the number of vertices in the subtree of u that are in the same connected component as it.
The initial values of c_u can be computed using a single DFS.
Note that the component sizes s_i defined above are simply the c_u values of all vertices u that are not in the same component as their parent (as well as the root).
Now, suppose the edge (x, p_x) is being updated (where p_x is the parent of x). We see that:
- If the edge is being added, the only change is that the value of c_u for several ancestors of p_x must increase by c_x.
More precisely, find the first ancestor of p_x that’s not in the same component as its parent (call this v) - then all vertices on the path from p_x to v must have their values increased by c_x. - If the edge is being removed, the exact opposite happens: once the appropriate v is found, all vertices from p_x to v will have their values decreased by c_x instead.
After each update, the change to component sizes is quite easy to figure out - only the components corresponding to x and v will change sizes, after all.
The necessary updates and queries can be handled with heavy-light decomposition (or even just Euler tour and a plain segment tree/fenwick tree).
For a full solution, bits are independent so simply run the above solution 20 times, once for each bit.
TIME COMPLEXITY:
\mathcal{O}(20\cdot N\log N) per testcase.
CODE:
Author's code (C++)
// ॐ
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pb push_back
const int N = 1e5 + 7;
const int MX = 1e6;
const int mod = 1e9 + 7;
struct DSUrb {
ll sz; vector<int> e; void init(int n) { e = vector<int>(n+1,-1); sz = (n * (n - 1)) / 2; }
int get(int x) { return e[x] < 0 ? x : get(e[x]); }
int size(int x) { return -e[get(x)]; }
vector<array<int,4>> mod;
void inline rem(ll s) { sz += (s * (s - 1)) / 2; }
void inline ad(ll s) { sz -= (s * (s - 1)) / 2; }
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) { mod.pb({-1,-1,-1,-1}); return 0; }
if (e[x] > e[y]) swap(x,y);
mod.pb({x,y,e[x],e[y]});
rem(-e[x]); rem(-e[y]);
e[x] += e[y]; e[y] = x;
ad(-e[x]);
return 1;
}
void rollback() {
auto a = mod.back(); mod.pop_back();
if(a[0] == -1) return;
rem(-e[a[0]]);
e[a[0]] = a[2]; e[a[1]] = a[3];
ad(-e[a[0]]); ad(-e[a[1]]);
}
};
ll ans[N];
array<int, 3> ed[N];
array<int,2> qr[N];
int bt[N];
int n, q, bit;
struct DynaCon {
int SZ;
DSUrb D; vector<vector<pair<int,int>>> seg;
DynaCon(int n){ SZ = n; seg.resize(2*SZ);}
void init(int n){ D.init(n);}
void upd(int l, int r, pair<int,int> p) { // add edge p to all times in interval [l, r]
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l&1) seg[l++].pb(p);
if (r&1) seg[--r].pb(p);
}
}
void process(int ind) {
for(auto &t: seg[ind]) D.unite(t.first,t.second);
if (ind >= SZ) {
ans[ind - SZ] += (D.sz << bit);
} else process(2*ind), process(2*ind+1);
for(auto &t: seg[ind]) D.rollback();
}
};
void solvebit(){
int t = 0;
map<pair<int, int>, int> mp;
vector<array<int, 4>> ar;
for(int i = 1; i < n; i++){
bt[i] = ((ed[i][2] >> bit) & 1);
if(!bt[i]) {
mp[{ed[i][0], ed[i][1]}] = 0;
}
}
for(int i = 1; i <= q; i++){
int in = qr[i][0], w = ((qr[i][1] >> bit) & 1);
if(w == bt[in]) continue;
int a = ed[in][0], b = ed[in][1];
if(!bt[in]) {
ar.pb({a, b, mp[{a, b}], i});
mp.erase({a, b});
} else {
mp[{a, b}] = i;
}
bt[in] = w;
}
for(auto &[a, b]: mp){
ar.pb({a.first, a.second, b, q + 1});
}
mp.clear();
DynaCon d(q + 1); d.init(n);
for(auto &t: ar){
d.upd(t[2],t[3],{t[0],t[1]});
}
d.process(1);
}
void solve() {
cin >> n >> q;
for(int i = 0; i <= q; i++) ans[i] = 0;
for(int i = 1; i < n; i++){
cin >> ed[i][0] >> ed[i][1] >> ed[i][2];
if(ed[i][1] < ed[i][0]) swap(ed[i][0], ed[i][1]);
}
for(int i = 1; i <= q; i++){
cin >> qr[i][0] >> qr[i][1];
assert(qr[i][1] <= MX); assert(qr[i][1] >= 0);
assert(qr[i][0] >= 1);
}
for(int i = 0; i < 20; i++){
bit = i; solvebit();
}
for(int i = 0; i <= q; i++){
cout << ans[i];
if(i != q) cout << " ";
else cout << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("input6.txt","r",stdin);
// freopen("output6.txt","w",stdout);
int t=1;
cin>>t;
while(t--)
solve();
}
Tester's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
ll nC2(int n){
return 1ll*n*(n-1)/2;
}
struct DSUrb {
vi e; ll sum;void init(int n) { e = vi(n,-1); sum = 0;}
int get(int x) { return e[x] < 0 ? x : get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
vector<array<int,4>> mod;
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) { mod.pb({-1,-1,-1,-1}); return 0; }
sum -= nC2(size(x));
sum -= nC2(size(y));
if (e[x] > e[y]) swap(x,y);
mod.pb({x,y,e[x],e[y]});
e[x] += e[y]; e[y] = x;
sum += nC2(size(x));
return 1;
}
void rollback() {
auto a = mod.back(); mod.pop_back();
if (a[0] != -1) sum -= nC2(size(a[0])),e[a[0]] = a[2], e[a[1]] = a[3],sum += nC2(size(a[0])),sum += nC2(size(a[1]));
}
};
const int N = 100005;
vector<ll> fin(N);
int pw = 1,n,q;
vpii seg[2*N];
DSUrb D;
void upd(int l, int r, pii p) { // add edge p to all times in interval [l, r]
for (l += (q+1), r += (q+1)+1; l < r; l /= 2, r /= 2) {
if (l&1) seg[l++].pb(p);
if (r&1) seg[--r].pb(p);
}
}
void process(int ind) {
for(auto t : seg[ind]) D.unite(t.ff,t.ss);
if (ind >= (q+1)) {
fin[ind-(q+1)] += pw*D.sum;
// do stuff with D at time ind-(q+1)
} else process(2*ind), process(2*ind+1);
for(auto t : seg[ind]) D.rollback();
}
int parent[N];
int siz[N];
void solve()
{
cin >> n >> q;
vector<array<int,3>> e(n-1);
rep(i,0,n-1){
int u,v,w;
cin >> u >> v >> w;
u--;v--;
e[i] = {u,v,w};
}
vector<array<int,2>> qr(q);
rep(i,0,q){
int e,w;
cin >> e >> w;
e--;
qr[i] = {e,w};
fin[i] = 0;
}
fin[q] = 0;
pw = 1;
int sm = 0;
auto oe = e;
vector<int> ls(n-1);
rep(j,0,20){
vector<bool> b(n-1);
e = oe;
rep(i,0,n-1){
if(!(e[i][2]&pw))b[i] = 1,ls[i] = 0;
}
D.init(n);
rep(i,0,2*(q+1)+1)seg[i].clear();
rep(i,0,q){
if((qr[i][1]&pw) != (e[qr[i][0]][2]&pw)){
if(b[qr[i][0]] == 0){
b[qr[i][0]] = 1;
ls[qr[i][0]] = i+1;
}
else{
upd(ls[qr[i][0]],i,{e[qr[i][0]][0],e[qr[i][0]][1]});
b[qr[i][0]] = 0;
}
}
e[qr[i][0]][2] = qr[i][1];
}
rep(i,0,n-1){
if(b[i]){
upd(ls[i],q,{e[i][0],e[i][1]});
}
}
process(1);
sm += pw;
pw *= 2;
}
rep(i,0,q+1){
fin[i] = 1ll*nC2(n)*sm - fin[i];
cout << fin[i] << " ";
}cout << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
while(t--)
solve();
return 0;
}