Hey all, I have been struggling with this question for quite a while now (almost three months) and there are no solutions that I can find online. It is from the Singaporean NOI qualification 2022 qualification test. The problem is described in the title —
given a tree, find the maximum diameter of the tree if you can remove one edge, and put that edge anywhere else. However, in the end, it must remain a tree. This is the link to the problem which also contains two testcases. https://codebreaker.xyz/problem/treecutting
I have been able to do it in O(n*n) by brute force but it is too slow. Can anyone help? Any help will be greatly appreciated. Thank you!
Suppose there's an edge $$$e = (u, v)$$$ in the tree, and let $$$T(u, v)$$$ be the tree which contains $$$u$$$ after removing $$$e$$$. You just have to compute the following values:
$$$D(u, v) = $$$ diameter of $$$T(u, v)$$$.
$$$F(u, v) = $$$ distance to the furthest node from $$$u$$$ in $$$T(u, v)$$$.
So $$$2N-2$$$ values of $$$D$$$ and $$$F$$$ respectively since you can direct each $$$N-1$$$ tree edges in 2 ways, and the answer to your problem is $$$\max(D(u, v) + D(v, u) + 1)$$$ over all tree edge $$$(u, v)$$$.
Root the tree at an arbitrary vertex $$$r$$$.
First, compute all $$$D(u, v)$$$ and $$$F(u, v)$$$ for all directed edges $$$u \rightarrow v$$$ where $$$T(v, u)$$$ contains $$$r$$$, in decreasing order of depth.
Secondly, compute the remaining values in increasing order of depth.
Total complexity is $$$O(\textrm{# of vertices})$$$
Hello, thank you so much for your help. I understand part 1 and part 2 and half of part 3 — when I am ocmputing all D(u, v) and F(u, v) where T(u, v) contains r. But what I am not sure about is how do i compute D(v, u) and F(v, u) where T(v, u) contains r? My previous solution was also O(n*n) because I had previously realised 1, and 2, but did not know how to compute all D(u, v) and D(v, u) efficiently.
Suppose you've computed the values for the first phase.
When you're on node $$$u$$$, you just remember
the largest value $$$L_{D1}$$$ and
the second largest value $$$L_{D2}$$$, which possibly is equal to $$$L_{D1}$$$,
among $$$D(v, u)$$$ for all neighbors $$$v$$$ of $$$u$$$. Similarly, you remember
the largest value $$$L_{F1}$$$,
the second largest value $$$L_{F2}$$$, and
the third largest value $$$L_{F3}$$$.
among $$$F(v, u) + 1$$$ for all neighbors $$$v$$$ of $$$u$$$.
Then for all child $$$w$$$ of $$$u$$$, $$$D(u, w)$$$ is formed by either choosing one $$$D(u, v)$$$ or by attaching two $$$F(u, v) + 1$$$. You just greedily pick the largest of the values remembered as long as they're not equal. Same for $$$F(u, w)$$$.
You have to find for all nodes, the diameter of the tree rooted at this nodes subtree and the diameter of the tree formed by removing this node's subtree. Answer is max of sum ov these values over all nodes. You can do this using a dfs.
I am aware of that, but I am just not sure how to do this efficiently. Do you think you could help me with the specific algorithm? I don't have a lot of experience with this. Thanks!
Do you have access to submissions? I can send you my code and if the implementation is correct then I can explain it too
Yes I do, if you create an account to the website i linked in my original post you can submit your code there. But if you want I can submit and test it for you as well.