# 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.

## HackerEarth Multiple Subtrees <Liv.ai> problem solution.

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

### Second solution

`#include<bits/stdc++.h>using namespace std;vector<int>v[100005];int deg[100005]={0},pre[100005]={0},cnt[100005],par[100005];bool vis[100005];void dfs(int node){    vis[node]=1;    for(int i=0;i<v[node].size();i++)    {        int u=v[node][i];        if(vis[u])continue;        deg[node]++;        cnt[u]=cnt[node]+1;        par[u]=node;    }    pre[node]=pre[par[node]]+deg[node];    for(int i=0;i<v[node].size();i++)    {        int u=v[node][i];        if(vis[u])continue;        dfs(u);    }}int main(){        int n,q;        cin>>n;        assert(n>=1 && n<=1e5);        for(int i=1;i<n;i++)        {            int x,y;            cin>>x>>y;            v[x].push_back(y);            v[y].push_back(x);            assert(x>=1 && x<=n);            assert(y>=1 && y<=n);            assert(x!=y);        }        cin>>q;    //cout<<v[1].size()<<"\n";    //cout<<v[2].size()<<"\n";        assert(q>=1 && q<=1e5);    par[1]=0;    cnt[1]=0;dfs(1);int u=2;    //cout<<par[2]<<"\n";        while(q--)        {            int x;            cin>>x;            assert(x>=1 && x<=n);        cout<<deg[x]+pre[par[x]]-cnt[x]<<"\n";        //if(x==2){cout<<deg[x]<<" "<<pre[par[x]]<<" "<<cnt[x]<<"\n";break;}            //cout<<v[x].size()<<"\n";        }    return 0;}`