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]

Description

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.

Input

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

Output

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

Sample Input

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

Sample Output

0
1

HINT

[Submit][Status][Web Board]