Chenghiz's blog

An Interesting tree problem
By Chenghiz, history, 7 years ago, In English

I have been given a weighed undirected tree. For each subtree of this tree, I need to find the node from which the sum of distances to all other nodes in the subtree is minimum.

The no. of nodes in the tree is of the order of 10^5.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

You want centroid of every subtree, this problem was in some CF round last year.

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

    http://codeforces.com/contest/685/problem/B

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

    Woukd that not be the center of the subtree?

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

    I don't think centroid is the node from which the sum of distances to all other nodes in the subtree is minimum, atleast for a weighed tree.

    Example — Consider a linear tree 1 -> 2 -> 3 -> 4 -> 5. Let edge 4 -> 5 be 100 and all other edges be 1. Then, the required node is 4 while the centroid is 3.

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

      Cost with 4 is 100 + 1 + 2 + 3 = 106. Cost with 3 is 101 + 1 + 1 + 2 = 105.

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

        Oh, I got confused. Thanks for the explanation.

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

      I think the answer should literally be the centroid.

      coz it is one of the properties of centroid.

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

Similar Problem: https://www.hackerearth.com/challenge/competitive/march-circuits-17/approximate/special-nodes/

→ Reply