nipul1's blog

[SOLVED] Help in tree based Problem
By nipul1, history, 4 years ago, In English

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);
        }
    }
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 6   Vote: I like it +4 Vote: I do not like it

I solved this problem this way: The answer for the root is the number of neighbors of the root node. Let the current node be a, ancestor of a be b, and cnt be the number of neighbors of a (not counting the ancestor), then $$$ans[a] = ans[b] - 1 + cnt$$$.
$$$-1$$$ is needed to subtract the current node from the answer.

You should have written this

void dfs(int s, int prev) {
	visit[s] = 1;
	vals[s] = prev + T[s].size();
	if (s != 1) 
		vals[s] -= 2;
	for (auto x : T[s]) {
		if (!visit[x]) {
			dfs(x, vals[s]);
		}
	}
}

Here's a test that didn't work for you

5
1 2
1 3
2 4
2 5
1
5
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nipul1 (previous revision, new revision, compare).

→ Reply