[SOLVED] Help in tree based Problem

Revision en2, by nipul1, 2020-03-08 11:47:13

Problem

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English nipul1 2020-03-08 11:47:13 10
en1 English nipul1 2020-03-08 06:04:02 833 Initial revision (published)