### Halym2007's blog

By Halym2007, history, 10 months ago,

• +16

 » 10 months ago, # |   +8 i think 2-nd subtask seems Mo's algorithm.
 » 10 months ago, # |   +8 i also need solution
 » 10 months ago, # | ← Rev. 2 →   0 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
»
10 months ago, # |
Rev. 3   +10

Trivial. Run DFS N times.

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.

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))
}


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).

Now the previous solution is $O(N^2)$ on trees where some nodes have $O(N)$ neighbors, but it can still be salvaged.
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)$.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 What? Read again. We update all relevant $v$ in logarithmic time using a single fenwick tree update.I even wrote a pseudocode. How could that be time limit?
•  » » » » » 10 months ago, # ^ |   0 We don't. We dont iterate over v.We iterate ONLY over x. For each x we observe that if we root the tree on any v such that $p_i(v) < p_i(x)$ then the $sub_i(x)$ will always be the same so we dont need to compare each one.So we dont need to chack all N possible values of v. We just need to check four cases and solve each one in log time. Read the pseudo code.