Amazon SDE Challenge - April/ May 2022

Minimize difference

You are given a tree with Nvertices numbered from 1to N The th edge connects Vertex X and Vertex y bidirectionally You have to divide this tree into three connected components by cuttinc any two edges of the tree. Let the three components be C, C2 and C3 Let X, X2 and X3 be the XOR of all the vertices of the components C, C2 and C3 respectively

Task

Minimize the difference between the maximum and minimum xor values of the components In short, you have to minimize the value of max(X, X2 X3) min(X, X2 X3)

Notes

• A tree is an undirected. connected and acyclic graph.
• A set of nodes forms a connected component in a tree if any node from the set of nodes can reach any other node by traversing edges.
• The bitwise XOR of integers : and B A XOR B. is when A XOR B is written in base two. the digit in the 2ks place k 20i1if exactly one of A and B is 1 and C otherwise For example, XOR of (101)₂ and (110)₂, is (011)₂.
• Cutting an edge means partitioning the vertices of the tree into two disioint subsets. In other words. cutting an edge results in an increase in the number of connected components.

#include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#define MAX_N 3030
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vll vector<ll>
#define vvll vector<vll>
#define all(a) begin(a), end(a)
using namespace std;

ll n;
bool vis[MAX_N];
ll tree[MAX_N], level[MAX_N];
ll par[MAX_N][12];
vvll conn;
ll shortLCA(ll u, ll v) { //o(logn)
    if(level[u] < level[v]) swap(u, v);
    ll diff = level[u] - level[v];
    for(ll j = 0; diff; j++) {
        if(diff & 1) u = par[u][j];
        diff /= 2;
    }

    return u == v ? u : -1;
}

ll dfs(ll u) {
    vis[u] = true;
    tree[u] = u;
    for(auto& v : conn[u])
        if(!vis[v]) {
            level[v] = level[u] + 1;
            par[v][0] = u;
            tree[u] ^= dfs(v);
        }
    return tree[u];
}

ll solve(vpll& edges) {
    memset(vis, 0, sizeof(vis));
    memset(tree, 0, sizeof(tree));
    memset(par,0,sizeof(par));
    memset(level, 0, sizeof(level));

    conn = vvll(n + 1);
    for(auto& [u, v] : edges) {
        conn[u].push_back(v);
        conn[v].push_back(u);
    }

    level[1] = 1;
    dfs(1);

    for(int p = 0; p < 11; p++) {
        for(int u = 1; u <= n; u++) {
            par[u][p + 1] = par[par[u][p]][p];
        }
    }

    ll res = INT_MAX;

    for(ll cut1 = 2; cut1 <= n and res; cut1++) {
        for(ll cut2 = cut1 + 1; cut2 <= n and res; cut2++) {
            ll lca = shortLCA(cut1, cut2);
            ll t1, t2, t3;
            if(lca == cut1) {
                t1 = tree[cut1] ^ tree[cut2];
                t2 = tree[cut2];
                t3 = tree[1] ^ tree[cut1];
            } else if(lca == cut2) {
                t1 = tree[cut1];
                t2 = tree[cut2] ^ tree[cut1];
                t3 = tree[1] ^ tree[cut2];
            } else if(lca == -1) {
                t1 = tree[cut1];
                t2 = tree[cut2];
                t3 = tree[1] ^ tree[cut1] ^ tree[cut2];
            }

            res = min(res, max({t1,t2,t3}) - min({t1,t2,t3}));
        }
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc;
    cin>>tc;
    while(tc--) {
        cin>>n;
        vpll edges;
        for(ll i = 1, u, v; i < n; i++) {
            cin>>u>>v;
            edges.push_back({u,v});
        }

        cout<<solve(edges)<<'\n';
    }
    return 0;
}