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.

## Problem C: tree

Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 17 Solved: 1

[Submit][Status][Web Board]

## Description

## 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

한국어
中文
فارسی
English
ไทย

Anything about the Problems, Please Contact Admin:admin

All Copyright Reserved 2010-2013 ZJUT ONLINE JUDGE TEAM

GPL2.0 2003-2013 HUSTOJ Project TEAM

Anything about the Problems, Please Contact Admin:admin

All Copyright Reserved 2010-2013 ZJUT ONLINE JUDGE TEAM

GPL2.0 2003-2013 HUSTOJ Project TEAM