Yet Another Tree Problem

Revision en2, by YouKn0wWho, 2019-07-14 10:08:52

The following problem popped into my mind all of a sudden and I have no idea how to solve it.

You are given a weighted rooted tree with $$$n$$$ nodes. You need to find the number of unordered pairs of nodes $$$(u,v)$$$ such that

$$$weight\,of\, simple\, path\, from\, u\,to\, v = subtree\, weight\, of\, u +subtree\, weight\, of\, v$$$

$$$Constraints: 1<=n<= 10^5, -10^6<=edge\,weights<=10^6$$$

It will be really helpful if you can provide me with a solution.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English YouKn0wWho 2019-07-14 10:08:52 7 Tiny change: ' weighted tree w' -> ' weighted rooted tree w'
en1 English YouKn0wWho 2019-07-13 12:49:37 477 Initial revision (published)