MO's algorithm on tree

#include <bits/stdc++.h>

using namespace std;

static const int MAXN = 2e5 + 5;
static const int BLOCK = 320;

struct node
{
    int v, w;
    node(int vv = 0, int ww = 0) : v(vv), w(ww) {}
};

struct MO
{
    int l, r, id;
    MO() {}
    MO(int l, int r, int id)
    {
        this->l = l;
        this->r = r;
        this->id = id;
    }
    friend bool operator < (MO A, MO B)
    {
        int BA = A.l / BLOCK;
        int BB = B.l / BLOCK;
        return BA == BB ? A.r < B.r : BA < BB;
    }
} Q[MAXN];

vector <node> graph[MAXN];
int nodeVal[MAXN];
int nodeList[MAXN<<1], // stores node number w.r. to dfs time
    weight[MAXN],      // weight of each edge stores in the child node
    ST[MAXN],          // starting time
    ET[MAXN],          // finishing time
    dfsTime;

int l, r, ans[MAXN];
int box[MAXN];            // stores number of distinct integer in the range [L,R]
int frequencyWeight[MAXN]; // frequency of each element
int frequencyNode[MAXN];   // check a node already frequencyNodeited or not
int tnode, tquery;




void dfs(int u = 1, int p = -1)
{
    dfsTime++;
    ST[u] = dfsTime;
    nodeList[dfsTime] = u;
    for (auto &it : graph[u])
    {
        int v = it.v;
        int w = it.w;
        if (v == p)
            continue;
        nodeVal[v] = w;
        dfs(v, u);
    }
    dfsTime++;
    ET[u] = dfsTime;
    nodeList[dfsTime] = u;
}

void work(int pos)
{
    int u = nodeList[pos];
    int w = nodeVal[u];
    if (w > tnode)
        return;
    if (frequencyNode[u])
    {
        frequencyWeight[w]--;
        if (frequencyWeight[w] == 0)
            box[ w/BLOCK ]--;
        frequencyNode[u] = 0;
    }
    else
    {
        frequencyWeight[w]++;
        if (frequencyWeight[w] == 1)
            box[ w/BLOCK ]++;
        frequencyNode[u] = 1;
    }
}
inline int read()       { int a; scanf("%d", &a); return a; }

int main()
{
    tnode = read();
    tquery = read();
    for (int e = 1; e < tnode; e++)
    {
        int u = read();
        int v = read();
        int w = read();

        graph[u].push_back(node(v, w));
        graph[v].push_back(node(u, w));
    }
    dfs(1);
    for (int q = 0; q < tquery; q++)
    {
        int u = read();
        int v = read();
        if (ST[u] > ST[v])
            swap(u, v);
        Q[q] = MO(ST[u]+1, ST[v], q);
    }
    sort(Q, Q+tquery);
    l = 1;
    r = 0;
    for (int i = 0; i < tquery; i++)
    {
        int L = Q[i].l;
        int R = Q[i].r;
        int ID = Q[i].id;
        while (l > L)   work(--l);
        while (r < R)   work(++r);
        while (l < L)   work(l++);
        while (r > R)   work(r--);
        int b;  // find box
        for (int k = 0; ; k++)
        {
            if (box[k] < BLOCK)
            {
                b = k;
                break;
            }
        }
        for (int k = b*BLOCK; ; k++)
        {
            if (frequencyWeight[k] == 0)
            {
                ans[ID] = k;
                break;
            }
        }
    }
    for (int i = 0; i < tquery; i++)
        printf("%d\n", ans[i]);
}