树的基础练习题

题目描述

给定一颗 $n$ 个节点的有根树，节点编号为 $1\sim n$，其中 $1$ 号点是根节点。树上每个点有初始权值 $a_1,\dots, a_n$。

接下来有 $m$ 次操作，每次操作给出三个参数 $op_i,x_i,v_i$：

• $op_i=1$ 时，表示将 $x_i$ 及以 $x_i$ 为根的子树内的节点权值全部异或上 $v_i$；
• $op_i=2$ 时，表示将从 $x_i$ 到根节点的简单路径上的所有节点（包括路径端点）的权值全部异或上 $v_i$。

这 $m$ 次操作结束后，请你依次输出树上每个节点的最终权值 $a_1',\dots,a_n'$。

输入格式

第一行两个正整数 $n,m$，意义如题目描述。

接下来一行 $n-1$ 个以空格分隔的正整数 $p_2,p_3,\dots,p_n$，依次描述 $2\sim n$ 号节点的父亲节点编号。

接下来一行 $n$ 个以空格分隔的非负整数 $a_1,\dots,a_n$。

接下来 $m$ 行，每行三个以空格分隔的整数 $op_i,x_i,v_i$，描述一次操作。

输出格式

一行 $n$ 个以空格分隔的非负整数 $a_1',\dots,a_n'$，表示所有操作完成之后树上每个节点的最终权值。

样例输入

6 5
4 1 1 6 3 
12 3 20 12 11 9 
1 2 14
2 2 16
2 3 20
1 3 16
1 4 18

样例输出

8 15 16 14 27 25

数据范围

本题共包含 $10$ 个测试点。对于全部测试数据，$3\le n,m\le 10^5,0\le a_i,v_j\le 10^9,op_j\in\{1,2\},1\le x_j\le n,\forall 1\le i\le n,1\le j\le m,1\le p_2,p_3,\dots,p_n\le n$，保证构成一颗树。