the chat about WC2018 Task1

chatting history.txt

Remark: All the time is UTC+8.

Etaoin Wu, [13.03.18 08:24]
subtask 1: a path, so the answer is the sum of all edge weights

Etaoin Wu, [13.03.18 08:25]
subtask 2: one same tree repeating 3 times, equal to 3 * the distance, calculating the distance is O(n)

Etaoin Wu, [13.03.18 08:26]
subtack 3: a tree and a path, dis(a,b)=dep(a)+dep(b)-2 dep(LCA(a,b))+abs(L(a)-L(b))

Etaoin Wu, [13.03.18 08:26]
where L is the position in path(with weight) and dep() is the depth on that tree

Etaoin Wu, [13.03.18 08:28]
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+abs(L(a)-L(b)) where a, b in different subtrees of sons of p

Etaoin Wu, [13.03.18 08:30]
we do a DP on tree and calculate the 1st and 2nd maximal f(x)=dep(x)+L(x) and g(x)=dep(x)-L(x)

Etaoin Wu, [13.03.18 08:31]
to calculate answer, choose one f() and one g() to update the answer

Etaoin Wu, [13.03.18 08:32]
thus subtask 3 can be solved in O(n) time

Etaoin Wu, [13.03.18 14:40]
subtask 4: two trees.

Etaoin Wu, [13.03.18 14:41]
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+dis2(a,b)-2*dep(p) where a, b in different subtrees of sons of p, dep() is depth on the first tree, dis2(,) is distance on the second tree

Etaoin Wu, [13.03.18 14:42]
same as last subtask, dep(p) is useless

Etaoin Wu, [13.03.18 14:43]
and we need to put the effect from the first tree (which means dep(x)) on the second tree

Etaoin Wu, [13.03.18 14:44]
then we can find a way: for any node on second tree x, create a new node x' which have only one edge from x' to x. Its length is dep(x).

Etaoin Wu, [13.03.18 14:44]
so the problem is converted to this: mainlain some sets on a tree(converted second tree)

Etaoin Wu, [13.03.18 14:45]
which supports merging two sets C=merge(A,B) and query the maximal distance Dis2(A,B) which means "max{a in A, b in B} dis2(a,b)"

Martin, [13.03.18 14:46]
But doesn't dep(p) matter in the second tree? lca(a,b) in the first tree != lca(a,b) in the second tree

Etaoin Wu, [13.03.18 14:47]
we enumerate p right?

Etaoin Wu, [13.03.18 14:47]
[Reply to Etaoin Wu]
LCA(,) is the lca on the first tree

Martin, [13.03.18 14:48]
Yeah but when you do a DSU on tree in the second tree, don't you fix the LCA in the second tree too?

Martin, [13.03.18 14:48]
Or are the sets arbitrarily merged?

Etaoin Wu, [13.03.18 14:49]
we dont need DSU to keep the sets

Martin, [13.03.18 14:49]
I mean the small-to-large technique, whatever it's called

Etaoin Wu, [13.03.18 14:50]
we dont need it

Etaoin Wu, [13.03.18 14:50]
we can easily find a result: for a graph whose every edge length >= 0, a maximal distance over two sets A and B must be obtained by the endpoints of diameter of A and B

Etaoin Wu, [13.03.18 14:51]
so for any set we just need to maintain its endpoints of diameter

Etaoin Wu, [13.03.18 14:52]
using DSU on tree (or small-to-large technique) will cause a slow algorithm

Martin, [13.03.18 14:52]
I get it, okay

Etaoin Wu, [13.03.18 14:52]
so we get an O(nlogn) algorithm right?

Etaoin Wu, [13.03.18 14:52]
O(logn) for any dis2(,) query

Etaoin Wu, [13.03.18 14:53]
which any merge() over sets of tree2 will call dis(,) 4 times

Martin, [13.03.18 14:54]
How do you merge(a,b) quickly?

Etaoin Wu, [13.03.18 14:54]
Note that a set only storages endpoints of its diameter, let's call it (L,R)

Etaoin Wu, [13.03.18 14:55]
so merge(A,B) = longest of {dis(A.L,A.R), dis(B.L,B.R), dis(A.L,B.L), dis(A.R,B.R), dis(A.L, B.R), dis(A.R, B.L)} which dis(,) means on 2nd tree

Martin, [13.03.18 14:57]
Ohh, right

Etaoin Wu, [13.03.18 14:57]
so we finished subtask 4: tree+tree?

Etaoin Wu, [13.03.18 14:57]
any question?

Martin, [13.03.18 14:58]
No

Etaoin Wu, [13.03.18 14:58]
[Reply to Etaoin Wu]
actually dis2(,) can be solved by faster lca2(,) which can be optimized to O(1) per query using RMQ structure (ST table)

Etaoin Wu, [13.03.18 15:01]
subtask 5. tree + path + path

Etaoin Wu, [13.03.18 15:01]
lets call the tree 1st and call the paths 2nd and 3rd

Etaoin Wu, [13.03.18 15:02]
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+abs(L2(a)-L2(b))+abs(L3(a)-L3(b))-2*dep(p)

Etaoin Wu, [13.03.18 15:05]
for any subtree we maintain f11(x)=maximal(dep(a)+L2(a)+L3(a)), f12(x)=maximal(dep(a)+L2(a)-L3(a)), f21(x)=maximal(dep(a)-L2(a)+L3(a)), f22(x)=maximal(dep(a)-L2(a)-L3(a)), and the answer can be updated using 2*2*2*2 different ways

Etaoin Wu, [13.03.18 15:06]
(correctness by abs(x)=max(a,-a))

Etaoin Wu, [13.03.18 15:07]
then we solved st5 with an O(n) algorithm.

Etaoin Wu, [13.03.18 15:07]
subtask 6. 1st tree + 2nd tree + 3rd path.

Etaoin Wu, [13.03.18 15:08]
it's complex, so we try to convert it to the "tree + tree" subtask which we solved previously.

Etaoin Wu, [13.03.18 15:09]
we do a divide & conquer on the 3rd path and calculate all the path over the midpoint. now the problem is :

Etaoin Wu, [13.03.18 15:10]
find l <= mid, r >= mid, maximize dis1(l,r) + dis2(l,r) + len(l) + len(r), where len() denotes the distance to the midpoint

Etaoin Wu, [13.03.18 15:11]
then we can put the effect from the path on the 2nd tree: create a node x' for any node x where dis2(x,x') = len(x)

Etaoin Wu, [13.03.18 15:12]
but if we call the "tree+tree" subtask directly we will get a O(n^2) algorithm, for divide & conquer calls O(n) steps

Etaoin Wu, [13.03.18 15:13]
the problem is that most points on 1st tree and converted 2nd tree is useless in the calculation

Etaoin Wu, [13.03.18 15:16]
so we need to construct the auxiliary tree of 1st and converted 2nd and do DP on it

Etaoin Wu, [13.03.18 15:34]
which we got O(r-l) for any divide and conquer step

Etaoin Wu, [13.03.18 15:34]
the overall running time is O(nlogn*time of LCA)

Martin, [13.03.18 17:34]
Okay I get it

Etaoin Wu, [13.03.18 17:35]
and the next subtask i will translate later

Etaoin Wu, [13.03.18 20:44]
so you know "auxiliary tree" right?

Etaoin Wu, [13.03.18 20:44]
I'm not sure about its translation

Martin, [13.03.18 20:45]
I've never heard of it actually

Martin, [13.03.18 20:45]
Ohhh

Martin, [13.03.18 20:45]
Centroid decomposition?

Etaoin Wu, [13.03.18 20:45]
oops

Etaoin Wu, [13.03.18 20:45]
no

Etaoin Wu, [13.03.18 20:45]
when you are doing DP on tree

Etaoin Wu, [13.03.18 20:45]
the complexity is O(n)

Etaoin Wu, [13.03.18 20:46]
but most nodes on that tree is useless

Etaoin Wu, [13.03.18 20:46]
and we have a set of node, that's what we are interested in, lets call it A

Etaoin Wu, [13.03.18 20:47]
we can find a set B = A ∪ {lca(x,y) | x,y in A}

Etaoin Wu, [13.03.18 20:47]
and the size of B is O(|A|)

Martin, [13.03.18 20:47]
Isn't that centroid decomposition though?

Etaoin Wu, [13.03.18 20:48]
it's different

Etaoin Wu, [13.03.18 20:48]
[Reply to Martin]
if you use centroid decomposition in this step there is one more O(log) in the complexity

Martin, [13.03.18 20:49]
Anyway, go on

Etaoin Wu, [13.03.18 20:49]
this is an example

<photo> https://i.loli.net/2018/03/15/5aa9b36d035ff.jpg

Martin, [13.03.18 20:51]
Oh I get it now

Etaoin Wu, [13.03.18 20:51]
we can see that using B to dp will lead to an O(|A|) complexity

Etaoin Wu, [13.03.18 20:51]
[Reply to Martin]
is there a name of it? in chinese it's called 虚树 which means "auxiliary tree"

Etaoin Wu, [13.03.18 20:53]
to calculate B we can sort A with the dfs order (order same as DFN in tarjan's algorithm), and get LCA() of any A(i) and A(i+1)

Etaoin Wu, [13.03.18 20:55]
when solving subtask 6 we use divide&conquer right? we can use merging sort to avoid a more O(log) complexity when building auxiliary tree.

Etaoin Wu, [13.03.18 20:55]
and we come to subtask 7.

Etaoin Wu, [13.03.18 20:56]
if you do a naive centroid decomposition on the 1st tree, you will find it hard that the set of vertex was divided into many subsets (equal to the degree of the decomposition centroid)

Martin, [13.03.18 20:56]
[Reply to Etaoin Wu]
I don't think so, I've never seen a problem with it either

Etaoin Wu, [13.03.18 20:57]
https://www.google.com/search?num=30&newwindow=1&ei=c3qnWrTVLYnSjwSFt7SIAw&q=auxiliary+tree+site%3Acodeforces.com&oq=auxiliary+tree+site%3Acodeforces.com&gs_l=psy-ab.3...29631.29631.0.30091.1.1.0.0.0.0.250.250.2-1.1.0....0...1.1.64.psy-ab..0.0.0....0.62Qi36Bx-RM

Etaoin Wu, [13.03.18 20:57]
I found some results in CF, you can view this later.

Martin, [13.03.18 20:57]
The concept is very easy, I understand it

Etaoin Wu, [13.03.18 20:58]
yes

Etaoin Wu, [13.03.18 20:58]
then we do a three-degree cenvertion (I never saw this in English either) on the first tree

Martin, [13.03.18 20:59]
What's that?

Etaoin Wu, [13.03.18 20:59]
we need to convert a tree with a larger max-degree into a tree whose max-degree <= 3, and in this problem we need to keep the dis() property unchanged

Martin, [13.03.18 21:02]
[Reply to Etaoin Wu]
https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree this?

Etaoin Wu, [13.03.18 21:02]
no

Etaoin Wu, [13.03.18 21:02]
this convertion don't keep the dis() property

Etaoin Wu, [13.03.18 21:02]
<photo> https://i.loli.net/2018/03/15/5aa9b3a7c2902.jpg
the red ink means edge weight

Etaoin Wu, [13.03.18 21:03]
this is a segment tree structure

Etaoin Wu, [13.03.18 21:03]
and the grey vertex means new nodes, can be proven O(n)

Etaoin Wu, [13.03.18 21:04]
can you understand this?

Martin, [13.03.18 21:04]
And you do that for the children of every node, right?

Etaoin Wu, [13.03.18 21:04]
yes

Etaoin Wu, [13.03.18 21:04]
for every node degree > 3

Etaoin Wu, [13.03.18 21:05]
so when we do a centroid decomposition, the tree is divided into <=3 parts.

Etaoin Wu, [13.03.18 21:06]
[Reply to Etaoin Wu]
like this, we're going to find l r in different parts, maximize dis2(l,r) + dis3(l,r) + len(l) + len(r), where len() denotes the distance to the centroid

Etaoin Wu, [13.03.18 21:09]
[Reply to Etaoin Wu]
and DP on 1st and 2nd auxiliary tree: maintain f[1..3][1..3] which f[i][j] means maximal distance from ith part to jth part

Etaoin Wu, [13.03.18 21:09]
and it can be merged (and update to the answer) in 6*6*time of dis(,) time

Etaoin Wu, [13.03.18 21:10]
so we get an O(n log n * (time of LCA) * 36) algorithm.

Etaoin Wu, [13.03.18 21:14]
any questions?

Martin, [13.03.18 21:18]
[Reply to Etaoin Wu]
What does 'part' mean?

Etaoin Wu, [13.03.18 21:19]
we do a centroid decomposition on the 3rd tree

Etaoin Wu, [13.03.18 21:19]
the centroid divide the 3rd tree into 3 parts

Etaoin Wu, [13.03.18 21:19]
and we calculate the answer of path(x,y) where centroid is on path3(x,y)

Etaoin Wu, [13.03.18 21:20]
that means x,y are in different parts of the tree

Martin, [13.03.18 21:20]
Oh, yes, right

Martin, [14.03.18 01:42]
[Reply to Etaoin Wu]
I'm not very sure about the 2 * 2  * 2 * 2 part, because it only makes sense to pair f11 with f22 and f12 with f21

Martin, [14.03.18 01:43]
Because the answer is the maximum value of (f11(a) + f22(b)) or (f12(a) + f21(b))

Martin, [14.03.18 02:58]
Also they call the segment tree-ish method you describe similar to the one in the Wikipedia article I sent (左儿子右兄弟)

Etaoin Wu, [14.03.18 07:29]
[Reply to Martin]
it seems that it's correct

Etaoin Wu, [14.03.18 07:30]
[Reply to Martin]
with that left-child right-sibling method, you cannot keep the distance information unchanged

Etaoin Wu, [14.03.18 07:30]
I think this is correct too:

<photo> https://i.loli.net/2018/03/15/5aa9b402c4e2c.jpg
still, red and orange ink is edge weight

Etaoin Wu, [14.03.18 07:58]
I've read the markdown file and thank you for your awesome work.

Etaoin Wu, [14.03.18 08:05]
[Reply to Etaoin Wu]
I'm going to change the segment tree-ish method to this method

Etaoin Wu, [14.03.18 19:59]
one of my friends suggested such an idea:

Etaoin Wu, [14.03.18 20:01]
instead of Centroid Decomposition (in that we determin a centroid node), we can use "Centroid Edge Decomposition" in which any round of D&C we find an edge, maximizing min(node count on side1, node count on side2) and divide the tree into 2 parts

Etaoin Wu, [14.03.18 20:02]
and we can avoid the (A,B) (B,C) (C,A) loop

Martin, [14.03.18 20:19]
If you use that technique, you don't have to make the tree binary, right?

Etaoin Wu, [14.03.18 20:19]
[Reply to Martin]
you still need to make the tree binary

Martin, [14.03.18 20:20]
Oh right yes

Etaoin Wu, [14.03.18 20:20]
think of a star graph <菊花图 in chinese>

Etaoin Wu, [14.03.18 20:20]
and the complexity becomes O(n^2)

Martin, [14.03.18 20:21]
node count on side1 + node count on side2 = n always right?

Martin, [14.03.18 20:21]
or n + extra nodes to make the tree binary

Etaoin Wu, [14.03.18 20:21]
[Reply to Martin]
no

Etaoin Wu, [14.03.18 20:21]
when you D&C into a deeper level, the side1+side2 = the node count of this level (subtree)

Etaoin Wu, [14.03.18 20:22]
and number of "extra nodes to make the tree binary" is O(n)

Martin, [14.03.18 20:22]
Yep I see

Etaoin Wu, [14.03.18 20:23]
now we don't have 3 parts

Etaoin Wu, [14.03.18 20:23]
it becomes 2 parts because of "Centroid Edge Decomposition"

Martin, [14.03.18 20:25]
And what do we do after that?

Etaoin Wu, [14.03.18 20:25]
then we give every node a color, 1 and 2

Etaoin Wu, [14.03.18 20:26]
and we can ignore the 1st tree, maximize d2(x,y)+d3(x,y) where x,y have different color

Martin, [14.03.18 20:27]
The nodes on each side have the same color right?

Etaoin Wu, [14.03.18 20:27]
yes

Etaoin Wu, [14.03.18 20:30]
[ 图片 ]
let's call this structure a "diameter structure"

Etaoin Wu, [14.03.18 20:30]
and we do a DP on the 2nd tree, maintaining f1(p) and f2(p) means the diameter structure of color 1 and color 2 in subtree of p on the 1st tree

Martin, [14.03.18 20:30]
Don't you actually have to maximize d2(x,y)+d3(x,y)+distance_to_edge(x)+distance_to_edge(y)?

Etaoin Wu, [14.03.18 20:31]
yes

Etaoin Wu, [14.03.18 20:31]
we build a node x' where d2(x', x) = distance_to_edge(x) and d3(x', x) = 0 for any node x

Etaoin Wu, [14.03.18 20:31]
therefore the dis_to_edge() can be avoided

Martin, [14.03.18 20:32]
Yep, you're right, I see

Etaoin Wu, [14.03.18 20:32]
then it's a subtask tree+tree right?

Martin, [14.03.18 20:32]
So we use that and naively call the "tree+tree" subtask every time?

Etaoin Wu, [14.03.18 20:33]
we call "tree+tree" on two auxiliary trees

Martin, [14.03.18 20:34]
And this is O(nlogn) if we make the tree binary?

Etaoin Wu, [14.03.18 20:34]
yes

Etaoin Wu, [14.03.18 20:35]
[Reply to Martin]
O(nlogn*(time of LCA))

Martin, [14.03.18 20:35]
Yeah I mean the D&C part is O(nlogn)\

Etaoin Wu, [14.03.18 20:35]
and LCA can be solved with st table (O(nlogn) preprocessing and O(1) per query)

Martin, [14.03.18 20:36]
ST is actually <O(n), O(1)> for LCA but it doesn't matter much I gues

Martin, [14.03.18 20:36]
s

Etaoin Wu, [14.03.18 20:36]
[Reply to Martin]
that <O(n) O(1)> is ugly

Etaoin Wu, [14.03.18 20:36]
using that bitmask trick, maybe called "4 russians"

Martin, [14.03.18 20:37]
hahaha the total code length is going to be like 6kb, why not add a few hundred bytes

Etaoin Wu, [14.03.18 20:37]
one of my friends have wrote it

Etaoin Wu, [14.03.18 20:37]
7.9 kb total

Etaoin Wu, [14.03.18 20:37]
(his code style is ugly i think)

Etaoin Wu, [14.03.18 20:38]
http://uoj.ac/submission/228833

Martin, [14.03.18 21:12]
can you write some pseudocode for D&C on edges?

Martin, [14.03.18 21:12]
I want to add it to the article

Etaoin Wu, [14.03.18 21:13]
first let's assume the tree has max degree 3

Martin, [14.03.18 21:14]
it's rec(Graph) { find edge maximizing min(nodes on side1, nodes on side2); colour edges on side1 black; colour edges on side2 red; solve(side1,side2); rec(side1); rec(side2);} right?

Etaoin Wu, [14.03.18 21:14]
yes

Etaoin Wu, [14.03.18 21:16]
https://www.etaoinwu.win/jedojidahaqe.coffeescript