i think 2-nd subtask seems Mo's algorithm.

i also need solution

I have put forward a stupid solution which may help.

Consider they are rooted tree on $$$1$$$. And now the size of subtrees of $$$u$$$ on two trees are $$$sub1_x$$$ and $$$sub2_x$$$.

If we make $$$v$$$ the roots of the two trees,what will be $$$sub1'_x$$$ and $$$sub2'_x$$$ like?

Well,if $$$x$$$ is not an ancestor of $$$v$$$ on the tree $$$1$$$,$$$sub1'_x=sub1_x$$$.The situation is the same for the tree $$$2$$$.

From other degree,try to calculate each $$$x$$$'s contribution.

For those $$$v$$$ neither in $$$x$$$'s subtree in tree$1$ nor in $$$x$$$'s subtree in tree$2$,if $$$sub1_x > sub2_x$$$ there will be a contribution. (I will explain how to calculate it later)

And for those $$$v$$$ in $$$x$$$'s subtree in tree $$$1$$$,but not in $$$x$$$'s subtree in tree $$$2$$$,we can find out which subsubtree($$$x$$$ has many sons,right?If $$$v$$$ is son or grandson or grandgrandson of different sons of $$$x$$$,$$$sub1'_x$$$ will be different.It's easy to calculate them) $$$v$$$ is in,and try to find out whether to make a contribution or not.

If $$$v$$$ is in $$$x$$$'s subtree in both trees,it's a bit harder.And I have to introduce how to mark the contribution. Try to record the order a node is visited when doing DFS(I call it DFS sequence),and the constraint above will be like in a certain interval(or two).We can consider nodes as point on the two-dimension plain and mark contribution by adding a rectangle,which can be done use a segment tree.Go back to this situation,we can try to sort the order of the sons of $$$x$$$ in tree $$$2$$$ by the size of their subtrees so that it will be still a consistent interval on both dimension. So the total problem will be solved in $$$O(n \log n)$$$.

Maybe it's very complicated but I have tried my best.

I have to finish my homework so I can only code it tomorrow. T_T

Subtask 1

Trivial. Run DFS N times.

Subtask 2:

I didn't find anything easier for such a specific constraint, but maybe my general solution actually gives TLE and gives AC on this subtask.

Subtask 3

The graphs are paths. Define $$$p_i(u)$$$ as the position of $$$u$$$ in along the path in graph $$$i$$$ ($$$i$$$ can be $$$1$$$ or $$$2$$$). Now turn the problem inside out: For each $$$x$$$ ask "For which roots $$$v$$$ does $$$x$$$ verify $$$sub_1(x) > sub_2(x)$$$?".

Then we split into four cases:

1. $$$p_1(v) < p_1(x)$$$ and $$$p_2(v) < p_2(x)$$$
2. $$$p_1(v) < p_1(x)$$$ and $$$p_2(v) > p_2(x)$$$
3. $$$p_1(v) > p_1(x)$$$ and $$$p_2(v) < p_2(x)$$$
4. $$$p_1(v) > p_1(x)$$$ and $$$p_2(v) > p_2(x)$$$

For each case we can find exact expressions for $$$sub_i(x)$$$, so its easy to check the condition:

• For case 1, $$$x$$$ verifies the condition iff $$$N - (p_1(x) + 1) > N - (p_2(x) + 1)$$$
• For case 2, $$$x$$$ verifies the condition iff $$$N - (p_1(x) + 1) > p_2(x)$$$
• etc ...

Finally, for each $$$x$$$, we add 1 to all the $$$v$$$ that are needed. But this is too slow, so instead of adding $$$1$$$ to the index $$$v$$$, we can add $$$1$$$ to the position $$$(p_1(v), p_2(v))$$$, which can be implemented quickly using 2D Fenwick Tree.

In the end we just grab the results from the data structure.

for x = 1 ... N {
  if N-(p1(x)+1) > N-(p2(x)+1) {
    fenwick_update(0, p1(x), 0, p2(x))
  }

  // ... same for cases 2, 3 and 4 ...
} 

for v = 1 ... N {
  ans[v] = fenwick_query(p1(v), p2(v))
}

Subtask 4

Let's expand on the ideas from the previous subtask. For each $$$x$$$ we ask "for which roots $$$v$$$ does $$$x$$$ verify the condition?".

To do this we split by cases: "what is the next node in the simple path from $$$x$$$ to $$$v$$$ in each tree?" (this corresponds to comparing $$$p_i(v)$$$ and $$$p_i(x)$$$ in the previous subtask) . Let's call these two nodes $$$a_1$$$ and $$$a_2$$$. And also lets define $$$sub_{i,u}(v)$$$ to be the size of the subtree of $$$v$$$ on tree $$$i$$$ if the tree was rooted on $$$u$$$.

Then $$$x$$$ verifies the condition for that $$$v$$$ if $$$sub_{1,a_1}(x) > sub_{2,a_2}(x)$$$

We can use the 2D fenwick tree idea from before to add one to all the correct roots but now instead of using $$$p_i(v)$$$ we will use positions in a DFS pre-order.

The complexity is $$$O(\Sigma_x deg_1(x) \cdot deg_2(x))$$$ (times $$$log(N)^2$$$ from the 2D fenwick tree or just $$$log(N)$$$ if done offline).

This sounds like it's too much, but it's ok because $$$deg_i(x) \leq 3$$$, so it's at most $$$9N$$$ things to consider.

Also, given the subtree sizes on the rooting at node 1 of each tree, we can compute $$$sub_{iu}(v)$$$ in $$$O(1)$$$ using simple math if $$$u$$$ and $$$v$$$ are neighbors (it's either the same subtree size or N minus that plus one).

Subtask 5

Now the previous solution is $$$O(N^2)$$$ on trees where some nodes have $$$O(N)$$$ neighbors, but it can still be salvaged.

For each tree and each node, sort its children by subtree size on the rooting at node 1.

Now note that, for each $$$x$$$ and a fixed $$$a_1$$$, the appropriate condition will be met for some prefix/suffix of the possible $$$a_2$$$'s, so we can binary search for the cutting point.

Since those subtrees are contiguous on the list of children, they will also be contiguous on the DFS pre-order. This means that we don't need to do a different fenwick tree update for each one, but we can get them all in a single update. Thus, the amount of updates will be $$$O(N)$$$.