Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Largest path queries problem solution

YASH PAL, 31 July 2024
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

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;
}
coding problems solutions

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes