11695 - Flight Planning

[Alice_Italy]

I've been thinking and trying to code something since this morning and I'm stuck. Could anyone give me hints on how to solve this one? I know the algorithms to find a tree's diameter and everything that's needed, I guess. I just don't know really what to do. The book says "cut worst edge". But what turns an edge to be the worst? Plus, by "center of subgraph" does it means "not a leaf"? I've also tried to count diameters of subgraphs produced by each edge removed and could not see any relation between those subgraphs' diameter and that being the "worst edge". Please, please help

[morris821028]

by Dynamic programming in O(n).

I also spend a lot of time solving this problem. Finally, I think that maybe this problem same as
uva 10459 - The Tree Root. But it is more difficult than uva 10459.

I find some people that solved by brute-force.

1) find a edge on longest path
2) using the algorithm find two trees' diameter. O(n), you know.

but this way maybe O(n*n).

1. Try to make graph become a rooted tree
2. Find some information of each node.

For node X.
information 1: all X's son node max height(longest path).
information 2: the longest path from parent, but don't have X.

above, you will learn from uva 10459.

information 3: X's son's sub-tree regard as a new graph, how longest path in this graph?
information 4: (G) - (X's sub-tree) regard as a new graph, how longest path in this graph?

3. try cut every edge (i, j), then using information 1-4 find the longest path for two graph.

all step by O(n).