HackerEarth Largest path queries problem solution

1. x: Add a new node:
2. You are given an already-existing node x, assuming that there are N nodes in the tree till now. Now, add a new node numbered (N + 1) with node x as its parent.
3. x: You are given a node x. Determine the length of the largest simple path in the tree starting from node x.

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define endl "n"
#define PB push_back
#define fr(i,n) for(i=1;i<=n;++i)
#define rp(i,n) for(i=0;i<n;++i)

typedef vector<ll> vl;
const ll N = 100005;
const ll LGN = 18;


set<ll> g[N];
ll lv[N], dp[LGN][N], sub[N], a[N], nn, lvc[N], dis[LGN][N], n, par[N];

void dfs0(ll s, ll p)
{
    dp[0][s]=p;
    for(auto it:g[s]) if(it!=p) lv[it]=lv[s]+1, dfs0(it,s);
}

ll lca(ll x, ll y)
{
    if(lv[x]>lv[y]) swap(x,y);
    ll i, tp=lv[y]-lv[x];
    rp(i,LGN) if((1ll<<i)&tp) y=dp[i][y];
    if(x==y) return x;
    for(i=LGN-1;i>=0;i--) if(dp[i][x]!=dp[i][y])
        x=dp[i][x], y=dp[i][y];
    return dp[0][x];
}

ll dist(ll x, ll y)
{
    return lv[x]+lv[y]-2*lv[lca(x,y)];
}

void pre()
{
    ll i,j;
    lv[1]=0;
    dfs0(1,1);
    fr(i,LGN-1) fr(j,n) dp[i][j]=dp[i-1][dp[i-1][j]];
}

void dfs1(ll s, ll p)
{
    nn++, sub[s]=1;
    for(auto it:g[s]) if(it!=p) dfs1(it,s), sub[s]+=sub[it];
}

ll dfs2(ll s, ll p)
{
    for(auto it:g[s]) if(it!=p && sub[it]>nn/2) return dfs2(it,s);
    return s;
}

void decompose(ll s, ll p)
{
    nn=0;
    dfs1(s,s);
    ll cent = dfs2(s,s);
    par[cent] = (p==-1)?cent:p;
    lvc[cent] = (p==-1)?0:lvc[p]+1;
    ll tp=cent;
    dis[0][cent]=0;
    while(par[tp]!=tp) tp=par[tp], dis[lvc[cent]-lvc[tp]][cent]=dist(cent,tp);
    for(auto it:g[cent]) g[it].erase(cent), decompose(it,cent);
    g[cent].clear();
}

multiset<ll,greater<ll> > ms1[N], ms2[N];
multiset<ll,greater<ll> >::iterator it;

void upd()
{
    ll tp=n, cur;
    ms2[tp].clear();
    while(par[tp]!=tp)
    {
        if(par[tp]<=n)
        {
            cur = (*(ms1[tp].begin()));
            ms1[tp].erase(ms1[tp].find(dis[lvc[n]-lvc[tp]+1][n]));
            if((*(ms1[tp].begin()))!=cur)
            {
                ms2[par[tp]].erase(ms2[par[tp]].find(cur));
                ms2[par[tp]].insert(*(ms1[tp].begin()));
            }
        }
        tp = par[tp];
    }
    n--;
}

ll qry(ll x)
{
    ll rt, tp=x;
    rt = *(ms2[tp].begin());
    while(par[tp]!=tp)
    {
        if(par[tp]<=n)
        {
            it = ms2[par[tp]].begin();
            if((*it) == (*(ms1[tp].begin())))
                it++;
            rt = max(rt, (*it) + dis[lvc[x]-lvc[tp]+1][x]);
        }
        tp = par[tp];
    }
    return rt;
}

int main()
{
    ll i,q,t,tp, x;
    cin>>t;
    while(t--)
    {
        n=1;
        cin>>q;
        fr(i,q)
        {
            cin>>tp>>x;
            if(tp==1)
            {
                a[i]=-1;
                g[x].insert(++n), g[n].insert(x);
            }
            else
                a[i]=x;
        }
        pre(); 
        decompose(1,-1);
        fr(i,n) ms1[i].clear(), ms2[i].clear();
        fr(i,n)
        {
            tp=i, ms1[i].insert(0), ms2[i].insert(0), ms2[i].insert(0);
            while(par[tp]!=tp)
                ms1[tp].insert(dis[lvc[i]-lvc[tp]+1][i]), tp=par[tp];
        }
        fr(i,n) if(par[i]!=i) ms2[par[i]].insert(*(ms1[i].begin()));
        for(i=q;i>=1;i--)
        {
            if(a[i]==-1)
                upd();
            else
                a[i] = qry(a[i]);
        }
        fr(i,q) if(a[i]!=-1) cout<<a[i]<<endl;
    }
    return 0;
}