[Problem](https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/destructive-tree-explosion-45170564/)↵
↵
↵
~~~~~↵
My Approach↵
ans = 0↵
according to me if some node gets broken then all its children will become independent subtree hence , ans += number of children of this node;↵
and for all ancestors number of children -1 should be added to answer↵
↵
for solving queries I have precalculated answer for each of the node using ↵
following code↵
~~~~~↵
↵
↵
~~~~~↵
vector<int > T[100001];↵
int vals[100001];↵
bool visit[100001]={0};↵
void dfs(int s,int prev){↵
visit[s]=1;↵
vals[s]=prev+T[s].size();↵
if(s!=1) vals[s]--;↵
for(auto x: T[s]){↵
if(!visit[x]){↵
dfs(x,prev+T[s].size()-1);↵
}↵
}↵
}↵
↵
~~~~~↵
↵
↵
↵
↵
↵
~~~~~↵
My Approach↵
ans = 0↵
according to me if some node gets broken then all its children will become independent subtree hence , ans += number of children of this node;↵
and for all ancestors number of children -1 should be added to answer↵
↵
for solving queries I have precalculated answer for each of the node using ↵
following code↵
~~~~~↵
↵
↵
~~~~~↵
vector<int > T[100001];↵
int vals[100001];↵
bool visit[100001]={0};↵
void dfs(int s,int prev){↵
visit[s]=1;↵
vals[s]=prev+T[s].size();↵
if(s!=1) vals[s]--;↵
for(auto x: T[s]){↵
if(!visit[x]){↵
dfs(x,prev+T[s].size()-1);↵
}↵
}↵
}↵
↵
~~~~~↵
↵
↵
↵
