HackerEarth Dilku and Love Triangle problem solution

In this HackerEarth Dilku and Love Triangle problem solution Dilku, as we all know, is very fond of girls. This time, he is trapped into a love triangle!

Bhopu, his first love and the princess of fairytale kingdom, found out that Dilku is also dating someone else and hence is extremely angry on him, this time it's very serious. Afraid of Bhopu, Dilku ran away from his house and he is hiding somewhere. Bhopu wants to get Dilku punished, so she decided to send troops to find him.

Bhopu has infinite supply of troops. She is, after all, the princess and the only daughter of powerful King Raj!. The kingdom can be represented by an undirected graph with N cities and N-1 roads connecting these cities, where it is possible to go from any city u to any other city v by traversing one or more roads.

Now, Bhopu asks you to help her commanding the troops.

Initially, there are no troops in the cities. You are responsible for performing Q operations, each of one of the following two types:

1. Given cities u and v, send one troop to every city lying on the path between cities u and v. Once a troop has been sent to a city, it stays there and does not move for the whole process.
2. Given a city x, find the number of troops that have already been sent to city x before.

HackerEarth Dilku and Love Triangle problem solution.

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI >    VVI;
typedef long long int   LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))

#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N = int(1e6)+1;
const int LOGN = 20;
VI g[N];
int BIT[N],Start[N],End[N],DP[LOGN][N],len,level[N];
void update(int x,int add)
{
  for(;x<N;x+=x^(x&(x-1)))
    BIT[x]+=add;
}
int query(int x)
{
  int ret=0;
  for(;x>0;x=(x&(x-1)))
    ret+=BIT[x];
  return ret;
}
void dfs(int u,int p)
{
  Start[u]=++len;DP[0][u]=p;level[u]=level[p]+1;
  for(int i=0;i<SZ(g[u]);i++)
    if(g[u][i]!=p)
      dfs(g[u][i],u);
  End[u]=len;
}
int lca(int a,int b)
{
  if(level[a]>level[b])swap(a,b);
  int d = level[b]-level[a];
  for(int i=0;i<LOGN;i++)
    if((1<<i)&d)
      b=DP[i][b];
  if(a==b)return a;
  for(int i=LOGN-1;i>=0;i--)
    if(DP[i][a]!=DP[i][b])
      a=DP[i][a],b=DP[i][b];
  return DP[0][a];
}
int main()
{
  int n,q;
  si(n);si(q);
  for(int i=1;i<n;i++)
  {
    int u,v;
    si(u);si(v);
    g[u].PB(v);
    g[v].PB(u);
  }
  dfs(1,1);
  for(int i=1;i<LOGN;i++)
    for(int j=1;j<=n;j++)
      DP[i][j]=DP[i-1][DP[i-1][j]];
  while(q--)
  {
    int t;si(t);
    if(t==1)
    {
      int u,v;
      si(u);si(v);
      int LCA = lca(u,v);
      update(Start[u],+1);
      update(Start[v],+1);
      update(Start[LCA],-1);
      if(LCA!=1)update(Start[DP[0][LCA]],-1);
    }
    else if(t==2)
    {
      int x;si(x);
      dout(query(End[x])-query(Start[x]-1));
    }
  }
    return 0;
}