Pairs of Paths
Contest: Codeforces Round 703 (Div. 2)
Difficulty rating: 2600
Tags: combinatorics, data structures, dfs and similar, dp, trees

You are given a tree consisting of $$$n$$$ vertices, and $$$m$$$ simple vertex paths. Your task is to find how many pairs of those paths intersect at exactly one vertex. More formally you have to find the number of pairs $$$(i, j)$$$ $$$(1 \leq i < j \leq m)$$$ such that $$$path_i$$$ and $$$path_j$$$ have exactly one vertex in common.

Input format:
First line contains a single integer $$$n$$$ $$$(1 \leq n \leq 3 \cdot 10^5)$$$.

Next $$$n - 1$$$ lines describe the tree. Each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$ describing an edge between vertices $$$u$$$ and $$$v$$$.

Next line contains a single integer $$$m$$$ $$$(1 \leq m \leq 3 \cdot 10^5)$$$.

Next $$$m$$$ lines describe paths. Each line describes a path by it's two endpoints $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$. The given path is all the vertices on the shortest path from $$$u$$$ to $$$v$$$ (including $$$u$$$ and $$$v$$$).

Output format:
Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
The tree in the first example and paths look like this. Pairs $$$(1,4)$$$ and $$$(3,4)$$$ intersect at one vertex.

In the second example all three paths contain the same single vertex, so all pairs $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$ intersect at one vertex.

The third example is the same as the first example with two additional paths. Pairs $$$(1,4)$$$, $$$(1,5)$$$, $$$(2,5)$$$, $$$(3,4)$$$, $$$(3,5)$$$, $$$(3,6)$$$ and $$$(5,6)$$$ intersect at one vertex.

Example input:
5
1 2
1 3
1 4
3 5
4
2 3
2 4
3 4
3 5

Example output:
2

Example input:
1
3
1 1
1 1
1 1

Example output:
3

Editorial:
<spoiler summary="Hint1"> Root the tree. </spoiler> <spoiler summary="Hint2"> After rooting the tree, how does the intersection of two paths look? </spoiler> <spoiler summary="Hint3"> After rooting the tree, what are the two types of intersection? </spoiler>
<spoiler summary="Solution"> Let's root the tree at some vertex. Now the intersection vertex is lca for at least one path. <spoiler summary="Proof"> If the vertex wasn't lca for both paths it would mean that there are either two edges going up (which is impossible in a rooted tree) or they are going up by the same edge, but this would mean that this vertex parent is also an intersection point, so the paths are intersecting in at least $$$2$$$ points, so this is impossible too. </spoiler>
Now there are two types of intersections: with the same lca and different lca. Let's count them independently.
For each path and it's lca let's find the subtrees that path goes to from lca. This would result in a triplet $$$(lca, subtree1, subtree2)$$$ (replace subtree with $$$-1$$$ if there is none) with $$$subtree1 < subtree2$$$ or both of them are $$$-1$$$.
Now to count the intersections of the first type let's use inclusion-exclusion principle. Remember all paths that have same lca. Now we need to calculate the number of pairs so that they have different $$$subtree1$$$ and $$$subtree2$$$ (or $$$-1$$$). The formula is going to be $$$cntpath \cdot (cntpath - 1) / 2 - \sum \left(cnt(subtree1, x) + cnt(x, subtree2) - (cnt(subtree1, subtree2) + 1) \right) / 2$$$ (from inclusion-exclusion principle) where cntpath is the number of paths with this lca and $$$cnt(x, y)$$$ is the number of paths with triplet $$$(lca, x, y)$$$. The situation with $$$-1$$$ is pretty similar, left as an exercise to the reader.
Finding the number of intersections of second type is a bit easier. We just need to calculate the number of all intersections between a path with fixed lca and a vertical path which crosses this lca (the path is not neccessarily vertical, but it contains both lca and it's parent) and then subtract $$$cnt(subtree1)$$$ and $$$cnt(subtree2)$$$, where $$$cnt(x)$$$ is the number of vertical paths that go into subtree $$$x$$$.
After that we just have to print out the sum of this two numbers. Counting all the needed functions can be done using some data structure (small-to-large for example) or some subtree dynamic porgramming.
The resulting complexity is $$$O(Mlog^2M)$$$ or $$$O(MlogM)$$$ or even $$$O(M)$$$ if you're strong enough.
</spoiler>