vkditya0997's blog

Center of a tree
By vkditya0997, history, 8 years ago, In English

Hello everyone,
I have seen many problems which can be solved using tree center.
So, I would like to know about it.
If someone can provide resources or explain it here in comments, It would be great!

and also my approach for today atCoder Problem C was something like this : ( failed! )

  • Find an extreme of a diamemter of tree, This can be done by running a dfs from any arbitrary node. The node whose depth is highest is one of the extreme. ( Please correct me? )
  • find the diameter from this extreme ( the highest depth from this node ).
  • the nodes with the depth equal to the diameter are pushed into a vector ( let's say A ).
  • Now, for every node in the vector A, Run a dfs and count the no of nodes having depth greater than K. the minimum of these would be the answer.


Where did I go wrong?
Someone please help me?

Thanks in Advance

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

Comments Comments (9)
| Write comment?
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Consider a graph

0 1
1 2
3 2
3 4
5 4
6 5
7 6
8 7
10 9
11 9
12 9
13 9
14 9
14 4

with K = 2. Now, the extreme diameter is 8 (between 0 and 8), but the optimal solution is to pick vertices 9-14, none of which even lies on the longest path.

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

There is a very nice and easy to implement algorithm for finding center of a tree.

1) Push all the leaves in a queue.
2) Remove the top element and remove the edges , if new leaves form push in queue.
3) The last node to be pushed in the queue is the Center

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

    Doesn't work for all graphs, only for trees.

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

      Yeah by mistake I wrote graph.

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

        What all things can be done by finding the center of a tree? Can you give one or two applications?

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

          Popular example might be Problem ( I am not sure though as I haven't solved it but I have heard it can be solved by finding absolute center ) .

          Other problems generally ask directly for center after updates. I haven't really seen much problems on center.

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

    From what I've understood this will find a center, not necessarily all centers (i.e, if there exists a second). Can this algorithm be applied in a way that finds all centers?

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

In your second dfs, where you find the diameter using the extremal vertex, you should store the parents for every node. Then you can do this simple code to find the center after your dfs is finished:

current = vertex_with_maximum_distance
while dist[current] > diameter/2:
    current = parent[current]
center = current
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi! Late but I've tried to retrace the path from the end of the diameter to the point where the distance is half of the diameter. But this doesn't seem to work correctly. Can anyone please help me out with this?

            // Method1: WA for some reason
        int reqDepth = depth[diaEnd2] / 2;
        int temp = diaEnd2;
        while (temp != diaEnd1)
        {
            if (depth[temp] == reqDepth)
            {
                cout << temp << endl; // center found
                return;
            }
            temp = parent[temp];
        }

        // Method2: AC
        int temp = diaEnd2;
        while (depth[temp] > depth[diaEnd2] / 2)
        {
            temp = parent[temp];
        }
        cout << temp << endl; // center found
    → Reply