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


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>

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

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