SPOJ :PT07Z - Longest path in a tree

1

Can someone suggest some test cases where my code is failing?

Problem:SPOJ.com - Problem PT07Z

My Code Link:nGg5Sn - Online C++0x Compiler & Debugging Tool - Ideone.com

2

Can you explain your idea? From what I can see from your code, your DFS function returns the first leaf node that it encounters. To find the longest path in a tree, you DFS from the root to the deepest leaf node. Now, you consider this as the starting node in the DFS and find the deepest node. If you’re using the same idea then your DFS function is wrong.

1 Like
3

The idea is to find the diameter of the tree.
Basically, we do dfs two times .
First time we dfs from any random node and calculate the end node of first dfs .Say we get x1 as the end point .
d is the distance covered during the dfs.(not required in first dfs since we are interested in end point).

Second dfs: We choose starting node as x1 and again do dfs .this time we set d=0 and calculate the distance till end point and output d.
This is the required distance.

I have tried many random test cases but none is falilng ,but on submission it gives WA.

4

You have written the dfs function wrong. Here’s a link to my solution for reference 1ak2ic - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like
5

Can you tell what is wrong in my code ???That will be very helpful.

6

Ok thanks, I understood, I was not calculating the max…