Автокомментарий: текст был переведен пользователем Temirulan (оригинальная версия, переведенная версия, сравнить).

Никто не знает? :(

I think my thoughts can help.

Let s1[v] be the sum of distances from first tree root to vertex v, similarly s2[v] the sum in second tree

s1[x] + s1[y] - 2 * s1[lca₁(x, y)] < s2[x] + s2[y] - 2 * s2[lca₂(x, y)]

then s1[x] - s2[x] - 2 * s1[lca₁(x, y)] < s2[y] - s1[y] - 2 * s2[lca₂(x, y)]

let a[v] = s1[x] - s2[x] and b[v] = s2[y] - s1[y]

a[x] - b[y] < 2 * s1[lca₁(x, y)] - 2 * s2[lca₂(x, y)]

I'm sure that is the correct way to solution

f(x, y) — расстояние между x и y в первом дереве, g(x, y) — расстояние между x и y в первом дереве. опечатка

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

А есть вообще основания полагать, что эта задача решается быстрее чем за квадрат?

One observation: we are actually looking for the number of pairs (x, y) such that f(x, y) = g(x, y).

UPD NVM is wrong.

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₂' such that for every node v in T₂, there is an edge (v, v') with weight d₁(p) - d₁(v), we have reduced our problem to finding the number of vertices that are within a distance D > 0 of each other.

However, the problem with this solution is that it would work in O(N²) if T₁ 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 that

If we attach an edge (v, v') with weight for all v to 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: .

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 M we want to count the number of pairs x ≤ M < y which satisfy f(x, y) < g(x, y). We have that g(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). Let v(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 M splits the active nodes in only 2 sets. If it were to split it K sets, like a normal centroid decomposition would, we would have an additional in time complexity, because when we query how many v(x)'s are less than a given value, we would also have to keep track of K colors, 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.