Yet Another Tree Problem

Правка en2, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский YouKn0wWho 2019-07-14 10:08:52 7 Tiny change: ' weighted tree w' -> ' weighted rooted tree w'
en1 Английский YouKn0wWho 2019-07-13 12:49:37 477 Initial revision (published)