Given $$$N$$$ cities connected by $$$N-1$$$ bidirectional roads i.e they form a tree . Cities with odd numbers are cities of Jack and even numbers cities belong to Bob. Each city has some initial popularity given by array Popularity. Now there are $$$Q$$$ tours taken by some tourists from city u to v taking the simple path.
As they travel from city u to v , the popularity of cities in between increases by x units. Let $$$P1$$$ and $$$P2$$$ be the sum of popularities of the cities of Jack and Bob after $$$Q$$$ tours . You need to print the absolute difference between P1 & P2.
$$$N \le 10^{5}$$$ $$$K \le 10^{6}$$$
I hope this won't be something that turns out to be misleading, however given the fact that we're talking about the nodes between two nodes on a tree, this leads me to think about something to do with LCA. However as I'm not quite sure about the maximum values of N and Q, I not sure about the final solution.
I have included the constraints now
You can break path u-v into u-lca(u,v) and v-lca(u,v). For each of these 2 sub-paths you can find how many nodes belong to jack and how many belong to Bob using binary lifting and update the sum accordingly
But we updated the nodes (given we increase values by x) . So how will we update those values ? When we make a query now we have new values of nodes, does that somehow lead to segment tree etc. ?
If there are c1 cities belonging to jack and c2 cities belonging to bob in some path increase p1 by c1 x X and p2 by c2 x X . Why do you need to update the node values ?
Oh shit!!!! . Got it . What I was doing was that lets say after first query value on some node increases by x , and after another query we have to make it 2*x and update our answer . Thank you
Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).
I think u r talking about rooted tree obiviously.
find initial difference.
Then for every query xx= no of between node using lca .
if x even no need to do anything as both side increases same. no of even node == no of odd node
else level of u and v node are same. its proved. so increase jack.bob points according to the u or v levels. So actually u don't need lca just check the level of u equal or not.