I have came across this problem recently (its statement is in Russian, please translate it) and couldn't find a good solution for it. Can anybody help me out? http://imcs.dvfu.ru/cats/static/problem_text-cpid-887909.html

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | apiadu | 3397 |

4 | TLE | 3374 |

5 | Um_nik | 3358 |

6 | 300iq | 3317 |

7 | maroonrk | 3232 |

8 | Benq | 3230 |

9 | LHiC | 3229 |

10 | 1919810 | 3203 |

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

1 | antontrygubO_o | 191 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 169 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 163 |

9 | 300iq | 156 |

10 | rng_58 | 154 |

I have came across this problem recently (its statement is in Russian, please translate it) and couldn't find a good solution for it. Can anybody help me out? http://imcs.dvfu.ru/cats/static/problem_text-cpid-887909.html

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/01/2020 18:35:27 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I will explain the statement shortly:

Given a tree with N node and a number D, calculate triples (u,v,w) such that

dist(u,v) =dist(v,w) =dist(u,w) = D.Constraint: N,D<=10^5.

http://informatics.mccme.ru/course/view.php?id=46

Year 2012-2013

day 2 D

Thanks alot!

Can you explain it in details? I'm not a Russian and I can't understand it well.

When i read this solution, i nothing understand. ;)

At first d mod 2 = 0

else print(0);

This problem equivalent next one:

Calculate four node (u, v, w, a) such that

dist(a, u) = dist(a, w) = dist(a, v) = d / 2

Then we calculate count node u such that dist(a, v) = d/2

each node a in DFS. (How, i not understand).

if

dis odd, answer is always 0. Otherwise:For each suitable triple, one node will be

`d/2`

-th parent of some node (lets call it center), and two others will be`d/2`

-th childs. So, if current center has`d/2`

-th parent and`x`

`d/2`

-th childs, then we can add`x(x-1)/2`

to our answer.How to calculate

`x`

? For each node, store its 2nd, 4th, etc parent, just like in well known LCA algorithm. Find`d/2`

-th parent in and add 1 to its`x`

.Overall complexity: time and memory

You are wrong describing all suitable triples that way. There can be no

`d/2`

-th parent of center, the path to it can be going up and then down.The idea to solution is following: in fact there are to options for suitable triple. Let's make tree rooted. It's easy to understand that there should be a center vertex

x:dist(a,x) =dist(b,x) =dist(c,x) =d/ 2.First option is that

a,bandclocated in three different subtrees ofx(then you should calculate sum of allsz[i] *sz[j] *sz[k] for this vertex, that's pretty easy).Second option is that

aandbare located in two different subtrees andcis somewhere in the subtree of vertex on the way fromxto the top. Let's call that vertexd(so,LCA(x,c) =d). Let's fixdand find all triples withd. That can be done using divide-and-conquer-on-tree technique.That's not correct. Did you read the editorial (there is a link above)?

Here is a solution that JWZMOZE came up with.

First observe that for any triplet (u,v,w) there is a central node x such that the distances (u,x), (v,x) and (w,x) are all D/2, and if you remove x then (u,v,w) end up all in diffent components. Thus you can solve the problem by computing for each node x the number of triplets with distance D/2 of x.

To compute the triplets, build a centroid decomposition of the tree. The decomposition is built by first selecting a central node x such that if you remove x, every component has at most n/2 nodes. Make x the root of the centroid decomposition, remove it from the tree and recursively perform the construction in remaining connected component.

While we are removing nodes as we build the decomposition, for every triplet (u,v,w) in the solution there is some point that removing the chosen node disconnects (u,v,w) into 2 or 3 components. Using this observation we can compute the total number of solution triplets as follows: Every time we choose a root node x for a subtree, count the number of triplets at distance D from each other that get separated into different components when x is removed. The solution is the sum of all the computed triplets after the whole centroid decomposition has been built.

To count the number of triplets that get separated when removing x, first compute an array containing the number of nodes at every distance from x. Also make the current subtree rooted at x, and in every node count the number of child nodes at distance D/2 from them. The number of separated triplets can be computed as a sum of two separate components:

x is the center node of the triplet. Then we need to count the number of triplets at distance D/2 of x such that each node of the triplet is in a separate component after removing x. To count that, first compute the number of triplets without the restriction that the nodes need to belong to different components, and then subtract from the number the number of triplets where 2 or 3 nodes are in the same subtree.

Some other node y is the center node. To count the number of such triplets, iterate over all other nodes in the current subtree. If a node y is at distance d from x, then the number of separated triplets is p*q, where p is the number of pairs of child nodes at distance D/2 from y, and q is the number of nodes at distance D/2-d from x in other subtrees than the one y belongs to.

By building the whole centroid decomposition, and at each step computing the number of these two types of removed triplets, we get the whole solution as every solution triplet gets separated exactly once. Overall complexity will be O(n log n), as each level of building the centroid decomposition can be done in linear time and the decomposition is guaranteed to have logarithmic height.

I had the same idea. It's a bit annoying with several situations where we need to subtract bad triples again, for example

in different subtrees of

y, even — but classic centroid otherwise.Writing about algorithms is so hard... ;_;

Well, it depends on experience. I, for example, don't find explaining my solutions hard probably because I've written many in Slovak for our correspondence seminar when I was younger, and the transition to English is just about knowing a language. Just like with practical coding (and actually, as part of it), it's something you get better at with practice.

What's exactly a correspondence seminar?

Several times a year, a set of problems are published on the net, people can solve them for about 2 months and the best 30+ from last 2-3 sets are invited to a camp (twice per year), which is partly for learning, but mostly for fun and getting to know others. And it's for primary/secondary school students.

In Slovakia (and Czech Republic, and maybe in other countries), there are many of them from many subjects. The programming one, KSP (you can see it as my Organisation) gives part of points for each problem for submited programs with IOI-scoring and part for writing a solution that described what the program's supposed to do, roughly proving why it works and complexity, and it's graded by people after a respective deadline.

What can be done if there was no restriction on D that is we had to find all equidistant triplets in a tree?

There was similar problem on CodeChef Long February Challenge and there also is an editorial

Can I get code for reference :)