HackerEarth Xor tree problem solution

In this HackerEarth Xor tree problem solution You are given an undirected tree with N nodes. Every node is initially assigned a value equal to 0.

Perform Q queries that are given on the tree as follows:

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.

Find the sum of values assigned to all the nodes after performing Q queries.

HackerEarth Xor tree problem solution.

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

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14, LG = 17;
int n, h[MAX_N], par[LG][MAX_N], a[MAX_N];
vector<int> g[MAX_N];

void dfs(int v = 0, int p = -1) {
    for (int u : g[v])
        if (u != p) {
            par[0][u] = v;
            h[u] = h[v] + 1;
            dfs(u, v);
        }
}

int lca(int v, int u) {
    if (h[v] > h[u])
        swap(v, u);
    for (int i = 0; i < LG; i++)
        if (h[u] - h[v] >> i & 1)
            u = par[i][u];
    for (int i = LG - 1; i >= 0; i--)
        if (par[i][v] != par[i][u])
            v = par[i][v], u = par[i][u];
    return v == u ? v : par[0][v];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int q;
        cin >> n >> q;
        fill(g, g + n, vector<int>());
        fill(a, a + n, 0);
        for (int i = 0; i < n - 1; i++) {
            int v, u;
            cin >> v >> u;
            v--, u--;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        dfs();
        for (int k = 1; k < LG; k++)
            for (int i = 0; i < n; i++)
                par[k][i] = par[k - 1][par[k - 1][i]];
        while (q--) {
            int v, u, w;
            cin >> v >> u >> w;
            --v;
            --u;
            int p = lca(v, u);
            while (v != p) {
                a[v] ^= w;
                v = par[0][v];
            }
            while (u != p) {
                a[u] ^= w;
                u = par[0][u];
            }
            a[p] ^= w;
        }
        cout << accumulate(a, a + n, 0ll) << 'n';
    }
}

coding problems