HackerEarth Xor tree problem solution

• u v w: For all the nodes present on a simple path between nodes u and v take the xor of node value with w. 

#include "bits/stdc++.h"
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) 
    for ( 
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); 
        blockTime.second; 
        debug("%s: %d msn", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false 
    )
#ifdef LOCAL
#include "pprint.hpp"
#endif
#define endl 'n';
#define pb push_back
#define mod 1000000007
#define ll long long int
#define prn(x) cerr<<x<<endl;
#define all(x) x.begin(),x.end()
using namespace std;
#define test_case 1

const ll N = 25;
ll n, res, cnt, node;
vector<ll> A, dpt;
vector<vector<ll>> g, par;

void init(){
    node=0;
    A.assign(n+1,0);
    dpt.assign(n+1,0);
    g.assign(n+1,vector<ll>());
    par.assign(n+1,vector<ll>(N+1,0));
}

void dfs(ll s, ll p){
    ++node;
    par[s][0]=p;
    for(int i=1;i<N;++i)
        par[s][i]=par[par[s][i-1]][i-1];
    for(auto x:g[s]){
        if(x==p)    continue;
        dpt[x] = 1 + dpt[s];
        dfs(x, s);
    }
}

ll lca(ll u, ll v){
    ll diff = abs(dpt[v]-dpt[u]);
    for(ll i=0;i<N;++i){
        if((1LL<<i)&diff)
            v = par[v][i];
    }
    if(u==v)
        return u;
    for(ll i = N-1;i>=0;--i){
        if(par[u][i]==par[v][i])
            continue;
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

ll dfs2(ll s, ll p){
    ll sum=0;
    for(auto x:g[s]){
        if(x==p)    continue;
        sum ^= dfs2(x,s);
    }
    A[s] ^= sum;
    return A[s];
}

void solution(){
    cin>>n;
    assert(n>=1 && n<=100000);
    ll q;
    cin>>q;
    
    init();
    // set<pair<ll,ll>> s;
    for(ll i=1;i<n;++i){
        ll u, v;
        cin>>u>>v;
        assert(u>=1 && u<=n);
        assert(v>=1 && v<=n);
        g[u].pb(v);
        g[v].pb(u);
    }
    
    dfs(1,0);
    assert(node==n);

    
    assert(q>=1 && q<=100000);
    for(ll i=1;i<=q;++i){
        ll u, v, w;
        cin>>u>>v>>w;
        assert(u>=1 && u<=n);
        assert(v>=1 && v<=n);
        assert(w>=0 && w<=1000000000);
        if(dpt[u]>dpt[v])
            swap(u,v);
        ll lc = lca(u, v);
        A[u] ^= w;
        A[v] ^= w;
        A[lc] ^= w;
        A[par[lc][0]] ^= w;
    }
    dfs2(1, 0);
    ll answer = 0;
    for(int i = 1 ; i <= n ; i++){
        answer += A[i];
    }
    cout << answer << endl;
}

int main(int argc, char *argv[])
{
    #ifdef LOCAL
        freopen("in.txt" , "r" , stdin);
    #else
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
    #endif

    int t=1;
    if(test_case)
        cin>>t;
    assert(t>=1 && t<=5);
    time__("Solution Time"){
        while(t--){
            solution();
        }
    }
    return 0;
}