Roronoa__Zoro's blog

By Roronoa__Zoro, history, 2 months ago, In English

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}$$$

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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. ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will we count the number of nodes belonging to Jack using Binary Lifting?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)].

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Roronoa__Zoro (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think u r talking about rooted tree obiviously.

  1. find initial difference.

  2. 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can you say that, if x is even, no of even node == no of odd node? I didn't get it.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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 values and now if you are at a node K and 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 add x*diff to the answer.