HackerEarth Largest path queries problem solution

In this HackerEarth Largest path queries problem solution You are given an unweighted tree that contains only 1 node. You have to process the following two types of queries:

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.

For each query of type 2, you must print the required answer. Note that the length of the path is equal to the number of edges in the path.

HackerEarth Largest path queries problem solution.

#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;
}