SleepingThread's blog

Tree Problem, is it solvable?
By SleepingThread, history, 3 years ago, In English

Hello everyone! I was solving a problem, but thinking in the wrong way, but I came up with this problem :

Given a 0-1 weighted tree that contains $$$N$$$ nodes $$$N <= 10^5$$$.

The value of a path is the sum of weights on this path.

For each node, find the number of simple paths which passes this node and have an odd value.

Have a good day!

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

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

the original problem (in case you thought I'm cheating, the marathon is over)

after hours of trying in the original problem, I realized that I don't need to do all of these things, but I thought it would be a good problem

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'll give the major hint that can solve this problem. There was an easier version of this in the Indian OI TC practice tests.

Root the tree arbitrarily. The idea is to assign a depth $$$dep_u$$$ to each node $$$u$$$ as the sum of weights along the path from $$$u$$$ to the root. Then for fixed $$$u$$$ the problem reduces to solving for the number of unordered pairs of nodes $$$x, y$$$ such that $$$u$$$ lies along the path from $$$x$$$ to $$$y$$$ and $$$dep_x, dep_y$$$ have different parities (so we can basically replace $$$dep_v$$$ with its parity for all $$$v$$$). Think about how you can do $$$\mathcal{O}(n)$$$ computations now for each subtree which can help you in computing the required value for each node.

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

rerooting

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

If it would help, I share my code which is written according to the editorial.

code
→ Reply