Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem C: tree

Problem C: tree

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 17  Solved: 1
[Submit][Status][Web Board]


Given a tree with N vertex and N-1 edges,each vertex i has a initial value 0. There are two types of operation:
1: given v and x, modify value of vertex v to x. In other words, w[v]=x.
2: given u,v and x. You should calculate how many vertex i that satisfy w[i] = x between the shortest path from u to v.


The first line contains one integer T, indicates the total test cases. Each test case starts with an integer N. Next N - 1 lines each line contains u and v, indicating there is an edge between u and v.
Then there is number q, indicating the number of operation.there are q lines followed.Each line first contain a number type, type = 1 or type = 2.If type equal 1, then followed v and x, otherwise there are 3 numbers u, v, x.

1<=N,q<=1e5,1<=type<=2,1<=x<=1e9,1<=u,v<=N,T = 5


For each operation of type 2, output one line contain answer.

Sample Input

1 2
2 3
2 2 1 1
1 3 1
2 1 3 1

Sample Output



[Submit][Status][Web Board]