[Gym] Problem F. Frank Sinatra

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Problem F. Frank Sinatra
                    Petrozavodsk Winter Training Camp 2016
Source            : Gym
Category          : Data Structure, Tree
Algorithm         : MO's Algorithm on Tree
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
static const int MAXN = 2e5 + 5;
static const int BLOCK = 320;
struct node
{
    int v, w;
    node() {}
    node(int v, int w)
    {
        this->v = v;
        this->w = w;
    }
};
 
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 timer, discover[MAXN], finish[MAXN], nodeTime[MAXN<<1];
 
int l, r, ans[MAXN];
int box[MAXN];       // stores number of distinct integer in the range [L,R]
int frequency[MAXN]; // frequency of each element
int vis[MAXN];       // check a node already visited or not
int tnode, tquery;
 
void dfs(int u = 1, int p = -1)
{
    timer++;
    discover[u] = timer;
    nodeTime[timer] = u;
    for (auto &it : graph[u])
    {
        int v = it.v;
        int w = it.w;
        if (v == p) continue;
        nodeVal[v] = w;
        dfs(v, u);
    }
    timer++;
    finish[u] = timer;
    nodeTime[timer] = u;
}
 
void work(int pos)
{
    int u = nodeTime[pos];
    int w = nodeVal[u];
    if (w > tnode) return;
    if (vis[u])
    {
        frequency[w]--;
        if (frequency[w] == 0) box[ w/BLOCK ]--;
        vis[u] = 0;
    }
    else
    {
        frequency[w]++;
        if (frequency[w] == 1) box[ w/BLOCK ]++;
        vis[u] = 1;
    }
}
 
inline int read()       { int a; scanf("%d", &a); return a; }
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    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 (discover[u] > discover[v]) swap(u, v);
        Q[q].l = discover[u] + 1;
        Q[q].r = discover[v];
        Q[q].id = 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 (frequency[k] == 0)
            {
                ans[ID] = k;
                break;
            }
        }
    }
    for (int i = 0; i < tquery; i++) printf("%d\n", ans[i]);
}