HackerEarth Multiple Subtrees Liv ai problem solution

In this HackerEarth Multiple Subtrees <Liv.ai> problem solution You are given a tree (not necessarily binary) with a special property which is, forming multiple sub-trees.

This happens as follows:

A random node of the tree is broken. After this, the node along with its immediate parents up to the root vanishes from the tree.

The tree has N number of nodes and nodes are numbered from 1 to N. The root of the tree is numbered as 1.

Given the number on one of its node, you have to tell the number of sub-trees that would be formed in-case the node is broken.

#ifndef _GLIBCXX_NO_ASSERT

#include <cassert>

#endif

#include <cctype>

#include <cerrno>

#include <cfloat>

#include <ciso646>

#include <climits>

#include <clocale>

#include <cmath>

#include <csetjmp>

#include <csignal>

#include <cstdarg>

#include <cstddef>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>





// C++

#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <iterator>

#include <limits>

#include <list>

#include <locale>

#include <map>

#include <memory>

#include <new>

#include <numeric>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <typeinfo>

#include <utility>

#include <valarray>

#include <vector>



#if __cplusplus >= 201103L

#include <array>

#include <atomic>

#include <chrono>

#include <condition_variable>

#include <forward_list>

#include <future>

#include <initializer_list>

#include <mutex>

#include <random>

#include <ratio>

#include <regex>

#include <scoped_allocator>

#include <system_error>

#include <thread>

#include <tuple>

#include <typeindex>

#include <type_traits>

#include <unordered_map>

#include <unordered_set>

#endif



using namespace std ;





//-------------------------------

typedef long long ll ;

typedef vector<int> vi ;

typedef pair<int,int> ii ;

//-------------------------------

#define _CRT_SECURE_NO_WARNINGS

#define pb(a) push_back(a)

#define mp(a,b) make_pair(a,b)

#define rep(i,a,b) for(int i=(a) ; (i)<(b) ; ++i)

#define inf 1e9

#define endl "n"

#define de(x) cerr<<#x<<" is "<<x<<endl;

#define max(a,b) ( (a>b) ? (a) : (b)  )

#define min(a,b) ( (a<b) ? (a) : (b)  )

//------------------------------
vi gr[111111] ;
int ans[111111],parent[111111],degree[111111],parent_c[111111];
int n,u,v,q;
void dfs(int x,int pa)
{
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i];
        if(u==pa) continue;
        degree[x]++;
        parent_c[u]=parent_c[x]+1;
        parent[u]=x;
    }
    ans[x]=ans[parent[x]]+degree[x];
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i];
        if(u==pa) continue;
        dfs(u,x);
    }
}
int main(){
    cin >> n ;
    rep(i,0,n-1){
        cin >> u >> v ;
        gr[u].pb(v); gr[v].pb(u);
    }
    cin >> q ;
    dfs(1,0);
    rep(i,0,q){
        cin >> u;
        //cout << degree[u] << " " << ans[parent[u]] << " " << parent_c[u] << endl ;
        cout << degree[u]+ans[parent[u]]-parent_c[u] << endl;
    }
}