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
How will we count the number of nodes belonging to Jack using Binary Lifting?
I meant using binary lifting to calculate LCA. To find the number of nodes you can simply use dfs to find d[u] which is number of nodes belonging to jack from root to node u and for specific path you can just do d[u] — d[lca(u,v)].
Yaa, got it. Thanks.
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.
How can you say that, if x is even, no of even node == no of odd node? I didn't get it.
He is trying to calculate the difference of Jack's and Bob's cities at every node from the root. In other words, let's say you have an array called
valuesand now if you are at a nodeKand it is odd, you just do something like-values[K] = values[par[K]]+1. If the current node K is even,values[K] = values[par[K]]-1. You can do this by just a simple dfs. By calculating the LCA of u and v you can easily find the difference of odd and even cities in that path-diff = values[u]+values[v]-values[par[lca(u, v)]]and just addx*diffto the answer.Thanks, I got it.