Doremy's Swapping Trees
Contest: Codeforces Round 906 (Div. 1)
Difficulty rating: 3500
Tags: dfs and similar, graphs, trees

Consider two undirected graphs $$$G_1$$$ and $$$G_2$$$. Every node in $$$G_1$$$ and in $$$G_2$$$ has a label. Doremy calls $$$G_1$$$ and $$$G_2$$$ similar if and only if:

- The labels in $$$G_1$$$ are distinct, and the labels in $$$G_2$$$ are distinct.
- The set $$$S$$$ of labels in $$$G_1$$$ coincides with the set of labels in $$$G_2$$$.
- For every pair of two distinct labels $$$u$$$ and $$$v$$$ in $$$S$$$, the corresponding nodes are in the same connected component in $$$G_1$$$ if and only if they are in the same connected component in $$$G_2$$$.

Now Doremy gives you two trees $$$T_1$$$ and $$$T_2$$$ with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$. You can do the following operation any number of times:

- Choose an edge set $$$E_1$$$ from $$$T_1$$$ and an edge set $$$E_2$$$ from $$$T_2$$$, such that $$$\overline{E_1}$$$ and $$$\overline{E_2}$$$ are similar. Here $$$\overline{E}$$$ represents the graph which is given by only reserving the edge set $$$E$$$ from $$$T$$$ (i.e., the edge-induced subgraph). In other words, $$$\overline{E}$$$ is obtained from $$$T$$$ by removing all edges not included in $$$E$$$ and further removing all isolated vertices.
- Swap the edge set $$$E_1$$$ in $$$T_1$$$ with the edge set $$$E_2$$$ in $$$T_2$$$.

Now Doremy is wondering how many distinct $$$T_1$$$ you can get after any number of operations. Can you help her find the answer? Output the answer modulo $$$10^9+7$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 2\cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the number of nodes in the trees $$$T_1$$$ and $$$T_2$$$.

Each of the following $$$n-1$$$ lines contain two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), representing an undirected edge in $$$T_1$$$. It is guaranteed these edges form a tree.

Each of the following $$$n-1$$$ lines contain two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), representing an undirected edge in $$$T_2$$$. It is guaranteed these edges form a tree.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, you should output a single line with an integer, representing the number of distinct $$$T_1$$$ after any number of operations, modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, there is at most one distinct $$$T_1$$$ having the only edge $$$(1,2)$$$.

In the second test case, you can choose the edge set $$$\{(1,3),(2,3)\}$$$ in $$$T_1$$$, the edge set $$$\{(1,2),(2,3)\}$$$ in $$$T_2$$$ and swap them. So $$$T_1$$$ can be $$$1-3-2$$$ or $$$1-2-3$$$.

In the third test case, there are $$$4$$$ distinct $$$T_1$$$, as the following pictures.

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

Example output:
1
2
4

Editorial:
We can construct a new directed graph, where we can consider each edge in $$$T_1$$$ and $$$T_2$$$ as a node. Let the node representing the edge $$$(u,v)$$$ in tree $$$T_i$$$ be $$$N(u,v,T_i)$$$.
For each node $$$N(u,v,T_1)$$$, let the simple path between $$$u$$$ and $$$v$$$ in $$$T_2$$$ be $$$(u_1,v_1),\dots,(u_m,v_m)$$$, and for all $$$1\le i\le m$$$ we add an edge from $$$N(T_1,u,v)$$$ to $$$N(T_2,u_i,v_i)$$$ in the new graph. And for each node $$$N(u,v,T_2)$$$, let the simple path between $$$u$$$ and $$$v$$$ in $$$T_1$$$ be $$$(u_1,v_1),\dots,(u_m,v_m)$$$, and for all $$$1\le i\le m$$$ we add an edge from $$$N(T_2,u,v)$$$ to $$$N(T_1,u_i,v_i)$$$ in the new graph.
Then we calculate the number of strongly connected components with the size bigger than $$$2$$$ in the new graph. If it is $$$t$$$, the answer is $$$2^t$$$.
To reduce the time complexity to $$$O(n\log n)$$$, we need to build the new graph with binary lifting or heavy-light decomposition or centroid decomposition or something like those. More specifically, we just build the data structure as normal, but replace the "modify" operation with "add edge" operation, which allows us to add edges from one node to a range of nodes with low time complexity.
Proof: it is obviously that the edge set we choose in each operation must be a closed subgraph in the new graph. And at the same time, it can be easily proved that every closed subgraph in the new graph is a valid edge set. The another thing we need to prove is that the set of valid closed subgraph won't change after an operation. We can easily prove this by the relationship between the number of edges and the number of nodes in a tree.