I'm trying to solve this problem about 3 days.Can you share your idea for subtasks.
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
I'm trying to solve this problem about 3 days.Can you share your idea for subtasks.
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.