ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

7460: Tokitsukaze and Colorful Tree

内存限制：128 MB 时间限制：16 S
题面：传统 评测方式：文本比较 上传者：
提交：3 通过：1
提交提交记录统计Web Board

题目描述

Tokitsukaze has a rooted tree with nnodes, whose nodes are labeled from 1to nand whose root is node 1. Furthermore, each node ihas its own color coliand its own weight vali, where the color is labeled as a number between 1and n, representing one of ngiven colors.
Here are two types of operation:
    ● 1xv-- set valxas v.
    ● 2xc-- set colxas c.
Tokitsukaze wants to execute qopeations and for i=1,2,…,q+1, after finishing the first (i−1)operations, she wants to know the value of

where ⊕is the bitwise exclusive OR operation.
If you are not familiar with the bitwise exclusive OR, you may refer to http://en.wikipedia.org/wiki/Bitwise_operation#XOR and http://baike.baidu.com/item/xor/64178.

输入格式

There are several test cases.
The first line contains an integer T(1≤T≤8), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains an integer n(1≤n≤105), denoting the number of nodes.
The second line contains nintegers, where the i-th intger is coli(1≤coli≤n), denoting the color of node iat the beginning.
The third line contains nintegers, where the i-th intger is vali(0≤vali<220), denoting the weight of node iat the beginning.
The next (n−1)lines describe the tree, where each line contains two integers uand v(1≤u,v≤n), representing an edge connecting node uand node v.
The next line contains an integer q(0≤q≤105), denoting the number of operations.
The next qlines describe these operations in chronological order of occurrence, where each line contains three integers such that
    ● if the first integer is 1, then the following two integers are xand v(1≤x≤n,0≤v<220), representing an operation of the first type, or
    ● otherwise the first integer is 2, and the following two integers are xand c(1≤x,c≤n), representing an operation of the second type.
It is guaranteed that the size of the standard input file does not exceed 32MiB, so you may need to use a fast approach to read the input data.

输出格式

For each test case, output (q+1)lines, where the i-th line contains an integer, denoting the value Tokitsukaze wants to know after the first (i−1)operations.

输入样例 复制 

1
5
1 1 1 1 1
1 2 4 8 16
1 2
3 1
2 4
2 5
2
1 3 32
2 3 2

输出样例 复制 

62
146
24

数据范围与提示


	
	

		For the only sample case:
● before the first operation, the value is (2 ⊕ 4) + (4 ⊕ 8) + (4 ⊕ 16) + (8 ⊕ 16) = 6 + 12 + 20 + 24 = 62;
● before the second operation, the value is (2 ⊕ 32) + (32 ⊕ 8) + (32 ⊕ 16) + (8 ⊕ 16) = 34 + 40 + 48 + 24 = 146;
● after all the operations, the value is 8 ⊕ 16 = 24.

分类标签