Easiest HLD with Subtree Queries

 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1E5 + 5;
const int logn = 19;
 
int tnode;
int tquery;
vector<vector<int>> graph;
vector<vector<int>> Tree;
int arr[maxn];
int subtreeSize[maxn];
int depth[maxn];
int father[maxn][logn];
int nxt[maxn];
int in[maxn];
int out[maxn];
int tym;
 
void makeTree(int u = 1, int p = 0) {
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        Tree[u].push_back(v);
        makeTree(v, u);
    }
}
 
void dfsSize(int u = 1) {
    subtreeSize[u] = 1;
    for (int &v : Tree[u]) {
        dfsSize(v);
        subtreeSize[u] += subtreeSize[v];
        if (subtreeSize[v] > subtreeSize[ Tree[u][0] ]) {
            swap(v, Tree[u][0]);
        }
    }
}
 
void dfs(int u = 1, int lvl = 1) {
    depth[u] = lvl;
    for (int i = 1; i < logn; i++) {
        father[u][i] = father[ father[u][i - 1] ][i - 1];
    }
    for (int v : Tree[u]) {
        father[v][0] = u;
        dfs(v, lvl + 1);
    }
}
 
void hld(int u = 1) {
    in[u] = ++tym;
    for (int v : Tree[u]) {
        nxt[v] = v == Tree[u][0] ? nxt[u] : v;
        hld(v);
    }
    out[u] = tym;
}
 
int findLca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (depth[ father[u][i] ] >= depth[v]) {
            u = father[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (father[u][i] != father[v][i]) {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
#define lchild  node * 2
#define rchild  node * 2 + 1
#define mid     (a + b) / 2
 
int STree[maxn * 4];
 
void update(int node, int a, int b, int pos, int val) {
    if (a > b or a > pos or b < pos) {
        return;
    }
    if (a >= pos and b <= pos) {
        STree[node] = val;
        return;
    }
    update(lchild, a, mid, pos, val);
    update(rchild, mid + 1, b, pos, val);
    STree[node] = STree[lchild] ^ STree[rchild];
}
 
int query(int node, int a, int b, int i, int j) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return STree[node];
    }
    int p = query(lchild, a, mid, i, j);
    int q = query(rchild, mid + 1, b, i, j);
    return p ^ q;
}
 
int queryUp(int u, int v) {
    // v = lca
    int xorsum = 0;
    int L = in[v];
    while (true) {
        int l = in[ nxt[u] ];
        int r = in[u];
        if (l <= L) {
            l = max(l, L);
            xorsum ^= query(1, 1, tnode, l, r);
            break;
        }
        xorsum ^= query(1, 1, tnode, l, r);
        u = father[ nxt[u] ][0];
    }
    return xorsum;
}
 
int queryHld(int u, int v) {
    int lca = findLca(u, v);
    int lft = queryUp(u, lca);
    int rgt = queryUp(v, lca);
    int middle = queryUp(lca, lca);
    return lft ^ rgt ^ middle;
}
 
void updateHld(int u, int val) {
    arr[u] = val;
    update(1, 1, tnode, in[u], val);
}
 
void init() {
    graph.clear(); graph.resize(maxn);
    Tree.clear(); Tree.resize(maxn);
    tym = 0;
    for (int i = 0; i < maxn; i++) {
        subtreeSize[i] = 0;
        in[i] = 0;
        out[i] = 0;
        nxt[i] = 0;
        memset(father, 0, sizeof father[i]);
        depth[i] = 0;
    }
    memset(STree, 0, sizeof STree);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    while (tc--) {
        init();
 
        cin >> tnode;
        for (int i = 1; i <= tnode; i++) {
            cin >> arr[i];
        }
        for (int e = 1; e < tnode; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        makeTree();
        dfsSize();
        dfs();
        nxt[1] = 1;
        hld();
 
        for (int i = 1; i <= tnode; i++) {
            updateHld(i, arr[i]);
        }
 
        cin >> tquery;
        while (tquery--) {
            int type;
            cin >> type;
            if (type == 1) {
                int u, val;
                cin >> u >> val;
                updateHld(u, val);
            } else {
                int u, v;
                cin >> u >> v;
                int xorsum = queryHld(u, v);
                cerr << xorsum << " ";
                cout << (xorsum ? "Alice" : "Bob") << endl;
            }
        }
    }
}
 

[Codechef] TAQTREE - Queries On Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : TAQTREE - Queries On Tree
Source            : Codechef
Category          : Graph Theory, Tree
Algorithm         : Easiest HLD Over Subtree and Paths 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 2e5 + 5;
static const int logn = 19;
 
struct Edge
{
      int v, w, id;
      Edge(int v = 0, int w = 0, int id = 0) : v(v), w(w), id(id) {}
};
 
vector <Edge> graph[maxn];
vector <int> Tree[maxn];
int subtreeSize[maxn], Id[maxn];
int depth[maxn], father[maxn][logn];
int nxt[maxn], in[maxn], out[maxn], tym, nodeCost[maxn];
 
void makeTree(int u = 1, int p = -1)
{
      for (Edge e : graph[u])
      {
            int v = e.v;
            int w = e.w;
            int id = e.id;
            if (v == p) continue;
            Tree[u].push_back(v);
            nodeCost[v] = w;
            Id[id] = v;
            makeTree(v, u);
      }
}
 
void dfsSize(int u = 1)
{
      for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
      for (int v : Tree[u])
      {
            dfsSize(v);
            subtreeSize[u] += subtreeSize[v];
            if (subtreeSize[v] > subtreeSize[ Tree[u][0] ]) swap(v, Tree[u][0]);
      }
}
 
void hld(int u = 1)
{
      in[u] = ++tym;
      for (int v : Tree[u])
      {
            nxt[v] = v == Tree[u][0] ? nxt[u] : v;
            hld(v);
      }
      out[u] = tym;
}
 
void dfs(int u = 1)
{
      for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
      for (int v : Tree[u])
      {
            depth[v] = depth[u] + 1;
            father[v][0] = u;
            dfs(v);
      }
}
 
int findLCA(int u, int v)
{
      if (depth[u] < depth[v]) swap(u, v);
      for (int i = logn - 1; i >= 0; i--)
      {
            if (depth[ father[u][i] ] >= depth[v]) u = father[u][i];
      }
      if (u == v) return u;
      for (int i = logn - 1; i >= 0; i--)
      {
            if (father[u][i] != father[v][i])
            {
                  u = father[u][i];
                  v = father[v][i];
            }
      }
      return father[u][0];
}
 
int segTree[maxn * 4];
int arr[maxn], N;
 
void update(int node, int a, int b, int pos, int val)
{
      if (a > pos or b < pos) return;
      if (a >= pos and b <= pos)
      {
            segTree[node] = val;
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = a + b >> 1;
      update(lft, a, mid, pos, val);
      update(rgt, mid + 1, b, pos, val);
      segTree[node] = segTree[lft] + segTree[rgt];
}
 
int query(int node, int a, int b, int i, int j)
{
      if (a > j or b < i) return 0;
      if (a >= i and b <= j) return segTree[node];
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = a + b >> 1;
      int p = query(lft, a, mid, i, j);
      int q = query(rgt, mid + 1, b, i, j);
      return p + q;
}
 
int queryUp(int u, int v)
{
      // u = niche, v = lca
      int sum = 0;
      int L = in[v];
      while (true)
      {
            int l = in[ nxt[u] ];
            int r = in[u];
            if (l <= L)
            {
                  l = max(l, L);
                  sum += query(1, 1, N, l, r);
                  break;
            }
            sum += query(1, 1, N, l, r);
            u = father[ nxt[u] ][0];
      }
      return sum;
}
 
int queryhld(int u, int v)
{
      int lca = findLCA(u, v);
      int lft = queryUp(u, lca);
      int rgt = queryUp(v, lca);
      int middle = queryUp(lca, lca);
      return queryUp(u, lca) + queryUp(v, lca) - 2 * queryUp(lca, lca);
}
 
void updatehld(int u, int val)
{
      nodeCost[u] = val;
      update(1, 1, N, in[u], val);
}
 
int main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
 
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
 
      int tnode;
      cin >> tnode;
      for (int e = 1; e < tnode; e++)
      {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].emplace_back(v, w, e);
            graph[v].emplace_back(u, w, e);
      }
      makeTree();
      dfsSize();
      nxt[1] = 1;
      hld();
      depth[1] = 1;
      dfs();
      N = tnode;
 
      for (int i = 1; i <= tnode; i++)
      {
//            cerr << i << ' ' << nodeCost[i] << ' ' << Id[i] << endl;
            updatehld(i, nodeCost[i]);
      }
 
      int q;
      cin >> q;
      while (q--)
      {
            int type;
            cin >> type;
            if (type == 1)
            {
                  int id, val;
                  cin >> id >> val;
                  updatehld(Id[id], val);
            }
            else
            {
                  int u, v;
                  cin >> u >> v;
                  cout << queryhld(u, v) << endl;
            }
      }
}