Regarding subway,

I got 100 pts,though my solution fails in one task that my friend said ,but the idea is the same for the correct solution with just minor modification to my solution.

first we need to know that reducing the edges to atmost 3,doesn’t change the ans -why?(just try it,if u dont get it ask(u will get it anyway ))

What i did was just stored 2 edges (correct solution stores 3 edges anyway).

Let dp[i][j][a][b] denote the maximum possible cost on the path from vertex i to 2^jth parent of i such that the path starts with the a^{th} edge of i,and ends at the b^{th} edge to j.

we can now calculate dp[i][j+1][a][b] by merging paths,i mean in order to find max cost to 2^{j+1}th parent of i,it is basically sum of max cost from i to 2^jth parent ,and 2^jth parent to 2^{j+1}th parent.

let us say i wanna calculate dp[i][j+1][0][1],

let par=2^jth parent of i,

dp[i][j+1][0][1]=max(dp[i][j][0][0]+dp[par][j][0][1]+(0th edge to j!=0th edge from j),

dp[i][j][0][1]+dp[par][j][1][1]+(1st edge to j!=1st edge from j),

dp[i][j][0][0]+dp[par][j][1][1]+(0th edge to j!=1st edge from j),

dp[i][j][0][1]+dp[par][j][0][1]+(1st edge to j!=0th edge from j),

)

edge to j means edge ending at j along the path i to 2^{j+1}th,and starting means edge starts at j along the path i to 2^{j+1}th.

Now u can easily answer the query (u,v),

calculate ans for path (u,lca(u,v)),(v,lca(u,v)) using similar strategy ,

And then merge it again taking that 0,1 cases like before.

For the correct code u probably would have to consider all cases for 3 edges.

My solution:

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