P8169 - Editorial

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

\sum_{x=1}^N \sum_{y=x+1}^N f(x, y)

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

\binom{n}{2} - \sum_{i=1}^k \binom{s_i}{2}

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