Roronoa__Zoro's blog

Tree Problem . Can anybody explain the approach Please
By Roronoa__Zoro, history, 5 hours 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

»
4 hours 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.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have included the constraints now

    → Reply
»
4 hours 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

→ Reply
  • »
    »
    4 hours 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. ?

    → Reply
    • »
      »
      »
      4 hours 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 ?

      → Reply
      • »
        »
        »
        »
        3 hours 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

        → Reply
»
4 hours 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).

→ Reply
»
33 minutes 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.

→ Reply