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

can anyone please help me and point out what I am doing wrong.

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

can anyone please help me and point out what I am doing wrong.

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

The answer should be 0 but your code will output 1.

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.

Sorry for the bad picture.

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.

instead use as follows

like

visited= vector (N,false);

adj.resize(N)

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];

vector adj[maxn];

int par[maxn];

int dep[maxn];

and reset for every test case like

for(i,0,n) adj[i].clear()

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 …

great explanation and again thanks for your advice