GM3234 yin-yang

The question ： Statistics do not repeat point pairs $(x,y)$ The number of , Satisfy $x$ To $y$ There is at least one on the path $z$ bring $z\to x$ and $z\to y$ The sum of the path weights of is $0$ .

Ideas ： Encounter such problems , We need to think about what is the number of root count pairs ; Then consider which algorithms can solve . Divide and conquer is a wonderful way to greatly simplify the problem on the tree .

details ： Point divide and conquer should take the center of gravity of the tree every time , In this way, the optimal . Pay attention to clearing . Pay attention to repeated statistics , Don't let it slip , And don't repeat .

practice ： The title says , Find one $z$ Point make $z\to x$ The sum of the weights of is $0$ meanwhile $z\to y$ The sum of the weights of is also $0$ . therefore You may wish to $p$ Root subtree Do some divide and conquer ： about $p$ The answer is Guarantee $LCA=p$ In this nature , All legal points are right $x,y$ The number of . set up $d[i]$ by $i$ The depth of the .

Observe , because $x\to y$ The highest point of the path is $p$ , therefore $d[z]$ Meeting $\ge d[p]$ （ Think about it , Why can it be equal to ） And it's a certain point $x$ perhaps $y$ The ancestors of the . So consider maintaining each node $i$ The precursor of $a[i]$ , It's defined as Closest to it , And not root One Node number bring $d[a[i]]=d[i]$ . It can be pre processed $d$ When , Use the bucket to calculate . Curious students may ask , Why? Not for the root ？ This is to facilitate the classification and discussion of different answers later , Please move the small bench and listen carefully .

that , Let's first discuss a special case , namely $x$ perhaps $y$ Is the answer of the root node .

1. Statistics have precursors （ Having a precursor means $a$ Not for $0$ ） all $x$ , send $x$ Satisfy $d[a[x]]$ by $0$ . Then we can turn it into $d[x]=0$ And there are precursors $x$ Number .

Discuss more general situations ：$x$ and $y$ be in Different sons of the root node Of subtree In .（ Because it's definitely not possible in the subtree of the same son ） therefore , We need to calculate by son , Every son , The first Its contribution to the answer minus —— Prevent duplicate contributions , Then calculate the answer , Again Add back the contribution .

2. When $x$ Have a precursor When , Statistics of all There is no precursor And qualified $y$ .

3. When $x$ Have a precursor When , Statistics of all Have a precursor And qualified $y$ , But because Will be counted twice , So store separately .

4. When $x$ There is no precursor When , At this time The precursor is the root node , therefore $d[x]=0$ , Statistics of all There is no precursor And meet the conditions $y$ , Because it will be counted twice , So store separately .

5. When $x$ There is no precursor When , Statistics of all Have a precursor And qualified $y$ , But because (2) Will be Repeated statistics , Therefore, it is not calculated .

The total answer can be calculated . Those answers stored separately need to be divided by $2$ , Add up to the total answer .

So how can we continue to divide and conquer , Guarantee the time complexity ？

When $p$ After calculating the answer of , You need to find the center of gravity of your son's neutron tree every time $y$ 了 . Next level recursion , It's calculation $y$ The answer , The results add up to the final answer . Why should we look for the center of gravity of the tree every time ？

prove ： The center of gravity of the tree is defined ： Focus $p$ , With $p$ Root , The maximum subtree size does not exceed $0.5\times size$ .

So the $p$ After calculation , It will be divided into at least two subtrees .

We know $n$ A complete binary tree of points has at most $\log n$ layer , So divide the tree according to the center of gravity , The number of layers is also $O(\log n)$ Class .

Calculation of each layer , need $O(n)$ Time for , So the total time complexity $O(n\log n)$ .

therefore , This question is ok $O(n\log n)$ A perfect solution （ The constant is slightly larger ）.