# Not able to get AC for TREEDIFF

https://www.codechef.com/viewsolution/33604155

this is my solution to Tree diff …similar to editorial approach …
but I am not even able to pass subtask

You are not considering the case when there are duplicate values on path say 1 2 4 6 8 2 3

for red path your code will give correct ans.
but for blue path your code will ans 1 while ans is 0.

As per your code you should change that set to vector.

1 Like

set contains vertices in the path and not weight on that node

I want to know how are you constructing the path between two nodes when that path contains<=100 nodes???You need to use lowest common ancestor using binary lifting technique

I have depth of each node and parent of each node …so i loop while parent of a and b are not equal

I have depth of each node and parent of each node …so i loop while parent of a and b are not equal

That’s why TLE is coming.I think that’s linear time.Will be ok for 1000 but after that it will give TLE.Use binary lifting

that why i have kept condition s.size>100 return 0 so it won’t process more than 100 nodes

Main Problem with your code is you are not clearing(resetting) all the vectors that you have used before.so for first test case code will work fine. but from 2nd test case on wards dfs will return from node 0 as it was visited in earlier test case.

There is no need of binary lifting. you can get AC without it.

Why TLE?
you are pushing back in all vectors for every new test case.

like
visited= vector (N,false);
parent=vector (N,-1)
same for parent and level

And best practice is to define the vectors of maximum size and use as you want and don’t forget to reset it like setting to 0 or -1.

like below

const int maxn=2e5+5;
int a[maxn];
int par[maxn];
int dep[maxn];

and reset for every test case like
for(i,0,n) par[i]=-1;

Here is your code I have edited first problem for you.
https://www.codechef.com/viewsolution/33617661

Here is my solution for reference
https://www.codechef.com/viewsolution/33556041

One more thing
add this lines at start in main function
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

it will make code faster.

Thank you very much for pointing out what i am doing wrong …