Why is there no editorial for TREEWLK2 problem from lunchtime 65? Can someone explain how to solve the problem?
I was a bit busy, so couldn’t complete editorial for that problem. I will post it as soon as i complete it. Please bear with me.
As for brief idea, Here you go.
We basically split paths of both persons. Say, First person have to cover distance 8 units to reach from 1ts to 2nd, 7 units to reach from 2nd to 3rd. And for Second person, 3 from 1st to 2nd, 3 from second to third, 4 from 3rd to 4th and 5 from 4th to fifth.
So, we will split the paths into parts. For first person, paths will be split as 3+3+2, 2+5. and for second person, paths will look like 3,3,2+2,5. Now, for every path, we calculate number of vertices shared. This can be done using lca queries, which i will explain in detail in editorial.
Also, handle direction of two people carefully.
I hope you don’t mind.
Eagerly waiting for the editorial of this problem.
I’ll complete as soon as I can.
Its okay, take your time.