[toph.co] City of Atlantis

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : City of Atlantis
Source            : toph.co
Category          : Graph Theory
Algorithm         : LCA, Binary Lifting
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb            push_back
 
static const int maxn = 1e5 + 5;
static const int logn = 19;
 
struct node
{
    int a, b;
    node(int a = 0, int b = 0)
    {
        this->a = a;
        this->b = b;
    }
};
 
vector <node> g[maxn];
node father[maxn][logn];
int depth[maxn];
 
inline void dfs(int u, int p=-1)
{
    for (int i = 1; i < logn; i++)
    {
        node ff = father[u][i-1];
        father[u][i].a = father[ff.a][i-1].a;
        father[u][i].b = __gcd(father[u][i-1].b, father[ff.a][i-1].b);
    }
    for (auto &it : g[u])
    {
        int v = it.a;
        int w = it.b;
        if (v == p) continue;
        father[v][0].a = u;
        father[v][0].b = w;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}
 
inline int query(int f, int p)
{
    for (int i = logn-1; i >= 0; i--)
    {
        node ff = father[f][i];
        if (ff.a != 0 && ff.b%p==0) f = ff.a;
    }
    return f;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc;
    scanf("%d", &tc);
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        int tNode;
        scanf("%d", &tNode);
        for (int i = 1; i < tNode; i++)
        {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            g[u].pb({v, w});
            g[v].pb({u, w});
        }
        depth[1] = 1;
        dfs(1);
        int tQuery;
        scanf("%d", &tQuery);
        printf("Case %d:\n", tcase);
        for (int q = 0; q < tQuery; q++)
        {
            int f, p;
            scanf("%d %d", &f, &p);
            int ans = query(f, p);
            printf("%d\n", ans);
        }
        for (int i = 0; i < maxn; i++)
        {
            g[i].clear();
            depth[i] = 0;
            for (int j = 0; j < logn; j++)
            {
                father[i][j].a = 0;
                father[i][j].b = 0;
            }
        }
    }
}