Aquacloud's blog

Need help! — tree problem.
By Aquacloud, 10 years ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

Year 2012-2013

day 2 D

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks alot!

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

if d is 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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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, b and c located in three different subtrees of x (then you should calculate sum of all sz[i] * sz[j] * sz[k] for this vertex, that's pretty easy).

    Second option is that a and b are located in two different subtrees and c is somewhere in the subtree of vertex on the way from x to the top. Let's call that vertex d (so, LCA(x, c) = d). Let's fix d and find all triples with d. That can be done using divide-and-conquer-on-tree technique.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    That's not correct. Did you read the editorial (there is a link above)?

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Here is a solution that kllp 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:

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

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    p is the number of pairs of child nodes at distance D/2 from y

    in different subtrees of y, even — but classic centroid otherwise.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Writing about algorithms is so hard... ;_;

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        What's exactly a correspondence seminar?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

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

    → Reply