kbcoder's blog

By kbcoder, history, 5 weeks ago, In English

UPD: So my doubt was resolved thanks to SirRembocodina, I updated my code to reflect that and I passed the 4th test case but got memory limit exceeded on test 5(2e5 values). I know, LOl right? As you know the directed tree one passed, with 2mb (ish) memory(memory limit 256 mb). The only difference here is the graph is undirected, so the adjacency list has twice the values. Shouldn't memory be only 2x also? code Any help is appreciated. Thanks

Prev: I was solving thisproblem. We are given a directed tree with every node reachable from 1(root). We calculate the number of leaf nodes and the sum of all weights of nodes in the subtree of each node. The thing is I took the tree as undirected because I was going to root at 1 anyway and do a dfs traversal — code, but this results in some node to have the number of leaves as 0(div by 0 error in code ultimately), the same code with the directed tree as in the Q works,here. I was wondering why? Arent these two traversals supposed to be the same as both trees are rooted at 1? Am I making some mistake in my implementation?

!

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

You know, you can try outputting the values and seeing what happens for yourself.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, should have seen the test case. I just assumed it was a big test case and I wont be able to figure out. My bad.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Well, I read your code. What happens is that you have wrong if-statement for leaves. You get the test where root has 1 adjacent vertex and it is recognized as a leaf and you exit without traversing the tree.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you have have added edges form (pi to i) and (i to pi) so your graph is not unidirected..

given in question --one way roads just add edges accordingly and change condition that (adj[u].size()==0 ) for checking leaf node ...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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