# 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 ms\n", 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 1const 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';    }}`