Hello There
I came across this problem on spoj
we're given a tree and we have to find two paths that don't share vertices and which sum of their length is maximum
no i got an idea where we compute the longest path for each subtree rooted with vertex u and there answer is the max sum for each node where for each node we sum the longest path in the subtree rooted with u and the longest path in the entire tree minus the sub tree rooted with u
the latter was a bit confusing for me and i couldn't come up with the solution
any advises or hints about how to compute the longest path in the tree minus the subtree rooted with u for each vertex u would be greatly appreciated
http://apps.topcoder.com/forums/?module=Thread&threadID=677305&start=0&mc=11
Yes exactly what i had in mind for computing the longest path in a subtree T`
but i couldn't really understand what he's doing when he's computing longest path in T/T`
Let dp[u][p] be the length of the longest path in a subtree u, where p is the parent of u. The answer is just dp[u][p] + dp[p][u]. To calculate dp[u][p], you may notice that the longest path must either be in a subtree c (c is a child of u) or goes through u. For the later case, you have to know the longest path in all the subtree c, starting at c.
so if p is parent of u ... answer is longest path in subtree of u + longest path in subtree p/u ?
how would that be the answer ?
Because the two paths don't share vertices, we can split the tree into two subtrees by cutting an edge. Then the two paths will be in different subtrees.
so p is the direct parent of u ? ... or every ancestor of u ?
p is the direct parent of u.
As DEGwer mentioned in this comment, you can see my code 16395328 for a better understanding.
This is the same as k790alex's idea, this code is also O(n2), not linear.
Oh, you're right. I just realized that TT
_and which sum of their length is maximum_They want two paths don't share vertices and which product of their length is maximum
typo
If you are still interested, I wrote a description in quora.
Your solution would probably time out even in C++, as the complexity is O(n2).
Consider a case in which vertex 1 is connected to all other vertices.
Edit: Wow, I just took a look at the editorial for that Codeforces contest and the official solution has the same complexity. Indian contests...
you are right, problems with bad tests cases allows this to pass (like the one in codeforces) :P.
Thanks.
We can keep linear time complexity if before running the described algorithm we binarize the tree, I mean adding dummy nodes to each node with more than two sons, in the worst case, N dummy nodes will be added, also this adds complexity to the code and may never pass SPOJ time limit.
Note that simply binarizing the tree before running the algorithm may change the final answer, which is not what you want.
You can probably get away with it if you treat dummy nodes and real nodes differently, but then the code gets considerably more complicated, because you're coding two different dfs functions instead of just one.
Once you've figured out exactly how to make this work, you should probably edit your quora answer to avoid spreading misinformation.
Edit: I coded what I think you meant by binarization in 16878650. Note that, in the dfs function, nodes with d != 0 are dummy nodes, and are treated differently than nodes with d == 0.
You are right, after binarizing the tree we need to handle 0/1 weights in the nodes (this is the same as the codeforces problem).
Is not difficult to handle the weights (I did it here 16865336), and the hash table becomes no necessary because the maximum degree of a node is 3.
I will describe the approach in quora later, and the problem you put is exactly the one in SPOJ with lower constraints.
I didn't put much attention to your code but is shorter of what I though, thanks.
I have some questions about your logic.
1- Why you are adding two dummy nodes per node?
2- What is the logic behind this (I think is related to previous question)?:
3- And finally, why are you erasing second deepest path length when a node is not dummy?
I actually think it would be much easier for you to write your own code if you have the idea, and it shouldn't be hard to make something clearer than what I did. In fact the answer to most of these questions is "because it was the first way I thought to code it".
For question 3, it's because you can't have a path go through the path between a parent and a child more than once.
For questions 1 and 2, I add two dummies for every edge (one in each direction). So if 1 connects to 2, 3, and 4, I'll have in the resulting tree:
So you can see the dummies form a line, d=-1 means we're coming from the right dummy, d=1 means we're coming from the left dummy.
Perhaps it's easier to say that each dummy represents a prefix (if d=-1) or suffix (if d=1) of the children of 1.
I did my own implementation and seems that I'm missing a corner case.
My logic is as follows: For each node having degree > 3 (parent and two sons) I add 1 dummy node, after this the node will have at most 3 links.
for a tree like this:
I will have this:
For each dummy node I compute the two deepest levels, this because a dummy node represents more than 1 son for the real node.
The longest path in a dummy node can include it only including the deepest level through the dummy author (the node that required to create this dummy node) and other deepest level (if exists).
I did several tests and is failing with bigger tests (non manually debugable).
Do you think my logic makes sense? Maybe I made a mistake in the implementation.
Thanks for your previous details.
I don't understand, sorry... What is this supposed to mean? "The longest path in a dummy node can include it only including the deepest level through the dummy author (the node that required to create this dummy node) and other deepest level (if exists)."
While creating a link(u, v) if degree(u) == 2 I add a dummy node to u to keep its degree in exactly 3, some like: u -> dummy1 -> v, in this case I say that dummy1 was created by u.
Nodes with label > 15 are dummy nodes. The following table shows the author of each dummy node:
Removing edge(15, 16) we have a path with length 4 starting at 15 (from 6 to 11), and a path of length 4 starting at 16, note that 16 is dummy and was created by 12, so the the we can use the path from 1 to 2.
Removing edge(12, 16) we can compute the longest path including 16 and it can be this (removing dummy nodes): 2, 7, 15, 6, 14. Which is not possible, see the original tree and edge(7, 15) doesn't exists, to reach 15 from 7 we need 12 which is the author of dummy node 16.
I submitted the code here: 16980218
I won't go into the code since it's very big, but a possible corner case is what happens when 2 dummy nodes connect.
When you cut edge(15,16), will you consider the path 13-19-20-7-2? It is a valid path (even though it doesn't go through 12).
Not really, author(19) = 16, so the path I will consider is deepestLevel(19), while doing dfs(19, 16) edge(19, 16) is cut, so the author of 19 is not reachable and I will consider only deepestLevel(19, 16) which is 2 (19, 20, 7, 2).
There should be a case I'm missing but I had no found it yet.
If a node is dummy, there are two cases:
Thanks.
As I said, 13-2 is a valid path, so if your code doesn't consider it for whatever reason the code is wrong.
Here is what I think (it might be wrong...) disconnect each edge of tree one by one...when u disconnect one edge u will get 2 trees...find diameter of each of tree and update answer to maximum of answer and sum of the 2 diameters...
I think 633F - The Chocolate Spree is almost same problem. It can be solved by tough tree dp but thinking how to merge data carefully lead me to correct solution. See 16678710.