← Home
write a go solution for Description:
You are given a tree consisting of n vertices. Initially, each vertex has a value 0.

You need to perform m queries of two types:

1. You are given a vertex index v. Print the value of the vertex v.
2. You are given two vertex indices u and v and values k and d (d<=20). You need to add k to the value of each vertex such that the distance from that vertex to the path from u to v is less than or equal to d.

The distance between two vertices x and y is equal to the number of edges on the path from x to y. For example, the distance from x to x itself is equal to 0.

The distance from the vertex v to some path from x to y is equal to the minimum among distances from v to any vertex on the path from x to y.

Input Format:
The first line contains a single integer n (2<=n<=2*10^5) — the number of vertices in the tree.

Next n-1 lines contain the edges of the tree — one per line. Each line contains two integers u and v (1<=u,v<=n; uneqv) representing one edge of the tree. It's guaranteed that the given edges form a tree.

The next line contains a single integer m (1<=m<=2*10^5) — the number of queries.

Next m lines contain the queries — one per line. Each query has one of the following two types:

- 1 v (1<=v<=n) — the query of the first type;
- 2 u v k d (1<=u,v<=n; 1<=k<=1000; 0<=d<=20) — the query of the second type.

Additional constraint on the input: there is at least one query of the first type.

Output Format:
For each query of the first type, print the value of the corresponding vertex.

Note:
The tree from the first example:

- "2 4 5 10 2": affected vertices are 4,2,5,1,3;
- "2 1 1 10 20" and "2 6 6 10 20": all vertices are affected, since distance to 1 (6) is less that 20 for any vertex;
- "2 3 2 10 0": affected vertices are 3,1,2;
- "2 5 2 10 1": affected vertices are 5,2,4,1.. Output only the code with no comments, explanation, or additional text.