NAACDI's blog

By NAACDI, history, 6 weeks ago, In English

We are given a tree with n nodes. Also at every node, we are given some numbers. We will process q queries, for each query we will be given 4 numbers, the type of the query(addition or subtraction, 1 — addition, 2 — subtraction), the starting node(we go up from this node), the size of the path(tells us at which ancestor of the starting node we finish), and some number p. The addition or subtraction for each node involved in the query will follow the Fibonacci sequence. Let's say x is the starting node, and up[x] is the ancestor of x, then the updates will go as follows: increase/decrease x by 1 * p, increase/decrease up[x] by 1 * p, increase/decrease up[up[x]] by 2 * p, increase/decrease up[up[up[x]]] by 3 *p, increase/decrease up[up[up[up[x]]]] by 5 * p... until we update all nodes on the path from x to the nth ancestor of x(where n is the length of the path). And for each query, we have to tell whether or not every number in the tree is equal to 0.

Constraints: n <= 200000 and q <= 100000
Ex: n = 6, q = 5, mod = 7
1 2
2 3
3 4
2 5
5 6
-2 -3 -1 3 1 1
1 3 3 4 - we increase the number at nodes 3, 2, and 1 (the array is 6, 1, 3, 3, 1, 1)
2 6 3 2 - we decrease the number at nodes 6, 5, and 2 (the array is 6, -3, 3, 3, -1, -1)
2 4 4 3 - we decrease the number at nodes 4, 3, 2, and 1 (the array is -3, -2 (-9 mod 7), 0, 0, -1, -1)
1 6 4 1 - we increase the number at nodes 6, 5, 2, and 1 (the array is 0, 0, 0, 0, 0, 0)
2 2 2 1 - we decrease the number at nodes 2 and 1 (the array is  -1, -1, 0, 0, 0, 0)
Answer:
0
0
0
1
0

For partial points, for each update, I run bfs from starting node going up, updating the values, and checking if they are all zero, for full points i guess we need O(n log n) or O(n).

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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