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>

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