HBD - Birthday Present
Today is problem setter's best friend Jenny’s birthday. Long ago, Jenny, being a very clever girl, asked the problem setter to perform some queries on a tree but he couldn’t do it. Now, he seeks your help to impress her on her birthday by answering those queries.
Recall that a tree is a connected acyclic undirected graph with n nodes and n-1 edges. In each node there are some flowers. The two type of queries are described as:
1 u v x
2 u y
For first type, you have to calculate the minimum number of vertices needed to be visited on the path from v to u, starting at v, to collect at least x(1<=x<=1e18) flowers, where v is a descendant of u. Note that you cannot visit any node that is not in the path from v to u and you cannot skip any node of the path from v to that node you've chosen at last. If it's impossible to collect at least x flowers visiting all the vertices from v to u then you have to print -1.
For second type, you have to add y(y can be negative) to the existing amount flowers in node u. It is guaranteed that after this operation, flowers in a node will be non-negative and sum of flowers of all node of the tree will be at most 10^18.
Note that 1 is the root of the tree.
The first line of the input contains two integers n(2 <= n <= 10^5) and q(1 <= q <= 10^5) where n is the number of vertices of the tree and q is the number of queries you have to perform.
Each of the next n-1 lines contains two integers a(1 <= a <= n) and b(1 <= b <= n) which denote an edge between a and b. The next line contains n non-negative integers c,c,..,c[n] (0 <= c[i] <= 10^13) where c[i] denotes the number of flowers in i’th node. Next q lines contain queries of the format described above.
For each query of the first type print minimum number of nodes you have to visit to collect at least x(1 <= x <= 10^18) flowers. If it's impossible to collect at least x flowers visiting all the vertices from v to u then print -1.
Input: 6 5 1 2 1 3 2 4 2 5 5 6 2 3 13 5 7 11 1 1 6 10 1 1 6 12 1 1 6 19 2 5 5 1 1 6 23
Output: 1 2 3 2