How do these 2 tree traversals differ?

Правка en2, от ora_ora, 2020-10-29 12:47:49

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?

UPD: So my doubt was resolved thanks to rembocoder, 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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ora_ora 2020-10-29 12:48:30 1059
en2 Английский ora_ora 2020-10-29 12:47:49 527
en1 Английский ora_ora 2020-10-28 22:17:00 841 Initial revision (published)