I'm trying to solve this problem about 3 days.Can you share your idea for subtasks.

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 168 |

3 | nor | 164 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | Um_nik | 162 |

7 | maroonrk | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

I'm trying to solve this problem about 3 days.Can you share your idea for subtasks.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 02:30:52 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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:

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

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.

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

In the third subtask.we see node 1<=v<=n every time?If yes i think its time limit.

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?

For every rooted node 1<=V<=n for every node X how we calculate fast sub1(x) > sub2(x)?

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.