Given two weighted trees. *f*(*x*, *y*) — distance between x and y in the first tree, *g*(*x*, *y*) — distance between x and y in the second tree. How many pairs (*x*, *y*) such that *x* < *y* and *f*(*x*, *y*) < *g*(*x*, *y*). Number of vertices <= 2*10^5.

I think my thoughts can help.

Let

s1[v] be the sum of distances from first tree root to vertex v, similarlys2[v] the sum in second trees1[x] +s1[y] - 2 *s1[lca_{1}(x,y)] <s2[x] +s2[y] - 2 *s2[lca_{2}(x,y)]then

s1[x] -s2[x] - 2 *s1[lca_{1}(x,y)] <s2[y] -s1[y] - 2 *s2[lca_{2}(x,y)]let

a[v] =s1[x] -s2[x] andb[v] =s2[y] -s1[y]a[x] -b[y] < 2 *s1[lca_{1}(x,y)] - 2 *s2[lca_{2}(x,y)]I'm sure that is the correct way to solution

Shouldn't the first equation and following contain

s1[lca_{1}(x,y)]and

s2[lca_{2}(x,y)]Yeap, but the task didn't get easier

You're looking for number of paths of positive value in weighted tree with weights g-f. Then you can do centroid decomposition or whatever.

EDIT: ah, sorry, I don't know why, but I assumed trees have same shape and differ just by weights. Ignore my post

"Given two weighted trees." What are you talking about?

Can you provide a link to the problem? Any ideas when all edges weights are the same ?

One observation: we are actually looking for the number of pairs (

x,y) such thatf(x,y) =g(x,y).UPDNVM is wrong.why?

The answer is where

resis the number of pairs (x,y) such thatf(x,y) =g(x,y).UPDNVM is wrong.Wut?

Consider N = 2. 1st tree is an edge with weight 10000. 2nd tree is an edge of weight 1. Are you telling that the answer is 1?

Yes, you are right.

Remark: This problem is similar to the one analyzed in this blog. You probably won't understand anything below unless you read it before.Let's fix , then we have to find the number of pairs such that . If we make a new tree

T_{2}' such that for every nodevinT_{2}, there is an edge (v,v') with weightd_{1}(p) -d_{1}(v), we have reduced our problem to finding the number of vertices that are within a distanceD> 0 of each other.However, the problem with this solution is that it would work in

O(N^{2}) ifT_{1}was a path.We can use the technique of "centroid decomposition on edges" and auxiliary trees to speed it up to . If

h(x) is the distance to the active edge while doing centroid decomposition, we have to find the number of pairs such thatIf we attach an edge (

v,v') with weight for allvto our auxiliary tree (which contains the vertices of tree 2 that we're currently processing), we have once again reduced the problem to finding the number of positive-length paths.Total complexity: .

"Let's fix

p=LCA_{1}(x,y) and never deal with that" is not a good way to solve a problem.I didn't understand anything but I also cannot understand anything in the previous article.

If legend Um_nik doesn't understand this, then this approach is wrong.

This solution is identical to bciobanu's. Can you point out the parts you don't understand? I am genuinely not sure why the relevant parts in the first article (i.e. "And finally [...] and so on." and "Let's start by [...]

O(|A|) nodes") are completely unintelligible. Unfortunately, I do not know of any English-language articles that talk about the concept of "auxiliary" trees. However, you can read the code for it here: https://blog.sengxian.com/algorithms/virtual-tree.Here's an idea in .

First suppose the second tree is a line tree. Let's relabel the nodes according to it, so that the edges will be

`1-2 2-3 3-4 .. N-1 - N`

.We'll divide and conquer over this line; for a fixed

Mwe want to count the number of pairsx≤M<ywhich satisfyf(x,y) <g(x,y). We have thatg(x,y) =g(x,M) +g(M,y). Root the first tree in an arbitrary node; we will make the following notation:f(x) =f(x,root).Re-writing the condition:

f(x) +f(y) - 2 *f(lca(x,y)) <g(x,M) +g(y,M). Letv(x) =f(x) -g(x,M). We'll re-write again:v(x) < 2 *f(lca(x,y)) -v(y).To follow-up with an alright complexity here, only some nodes of the divide-conquer from the second tree will be active at some step. We'll build the virtual tree (i'm not sure if this is how it's called in the folklore, here is one problem which mentions it in the editorial, perhaps you could go from there) consisting of these nodes in the other tree. Counting the number of good pairs can be done with a min-max-merge on this tree we've built.

Now, before we move on to arbitrary trees, note that we've used the fact that

Msplits the active nodes in only 2 sets. If it were to split itKsets, like a normal centroid decomposition would, we would have an additional in time complexity, because when we query how manyv(x)'s are less than a given value, we would also have to keep track ofKcolors, not only 2.Following up on arbitrary trees, we'll binarize the second tree while maintaining distances. To do this, we can root it in an arbitrary node and convert any adjacency list of length greater than 2 similar to a segment tree construction. This way, we preserve distances, while adding only

O(N) dummy nodes.Can you explain how do you find the number of good pairs in the virtual tree fast? Won't you need another inner centroid decomposition, but this time on the compressed/Virtual tree?

UPD:Nvm it can be easily done with DSU on tree and segment tree.Yeah, i was thinking the same, but on a second thought, i didn't quite get the complexity right.. this way we'll do .

However.. if we use sqrt buckets (keep the array sorted along with a buffer of at most elements) instead of ST for the DSU, we'd get .

You can reduce it to finding the number of positive-length paths by attaching a leaf

v' to each vertexv, where the edge (v,v') has a weight of , which is solvable by a simple centroid decomposition. (Our solutions only differ in that part, by the way)Well this was the inner centroid decomposition I was talking about. Unfortunately it's again .

You're right, it is actually but it may be possible to speed it up by using a faster integer sorting algorithm.

Let

d_{c}be the array of distances from centroidcto every one of its children. Also, letd'_{u}be the elements of that are inu's subtree. We have therefore reduced this problem to counting the number of pairs in an array with positive sum. Obviously, this runs inO(n+S(n)), whereS(n) is the time required to sortnelements. I think it may be possible to cheat here by using a fast integer sorting algorithm.As a last resort =)), binarize the virtual tree as well and when doing centroid decomposition, recurse first, and along with the result, get the values from the subtrees in sorted order and merge them in

O(N). This probably fixes the time complexity back to , but it's a headache.I feel like for an adequate book-keeping in a centroid step on the virtual tree we'll need some form of sorting.

It simply converts to number of paths of length ≤

Kwhich cannot be solved faster than with centroid decomposition.I'm not sure I got the sqrt decomposition way. Can you please explain it in some more details.

Btw the trick of using SQRT decomposition in such divide and conquers to reduce the complexity is really nice. Thanks for sharing it!

Following up on the , we need a data structure to perform:

KWe'll keep two arrays, namely

AandB. Whenever we insert a value, we'll push it to the back ofB. IfB's capacity exceeds , sort it, and then merge it with the elements fromAin . ForNinserts, its amortized complexity is .For a query, do binary search on

Aand brute search onB. It's .Now, when combining it with DSU:

T(N) =T(N-A) +T(A) + ??. Now, you'd normally replace ?? withmin(N-A,A). But it our case it's not convenient. If , then we'll merge the structures inO(N).If we'll push them regularly on to

Band if it exceeds, we do what we did above. This all amortizes to .I guess there are some other paths we could have chosen here. Another quick one would be keeping lists inside each DSU, the

i-th list representing the elements from , whereVis the sorted array with all costs. On a query we take the lists by hand and brute-force the current query element's list.