UOJ Logo Universal Online Judge

UOJ

#435. 【集训队作业2018】Simple Tree

统计

有一棵有根树,根为 $1$ ,点有点权。

现在有 $m$ 次操作,操作有 $3$ 种:

$1\ x\ y\ w$ ,将 $x$ 到 $y$ 的路径上的点点权加上 $w$ (其中 $w=\pm{1}$ );

$2\ x\ y$ ,询问在 $x$ 到 $y$ 的路径上有多少个点点权 $>0$ ;

$3\ x$ ,询问在 $x$ 的子树里的点有多少个点点权 $>0$ 。

输入格式

第一行三个数 $n,m,T$ ,表示树的结点个数,操作个数,和是否加密。

接下来 $n-1$ 行,每行 $2$ 个数 $x\ y$,表示结点 $x$ 和 $y$ 之间有一条边。

接下来一行 $n$ 个数,第 $i$ 个数表示结点 $i$ 的初始点权。

接下来 $m$ 行,每行格式见题目描述。

如果 $T=1$ ,则这 $m$ 行读入的每个 $x,y$ 都需要异或 $last\_ans$ 才能得到真实的输入,其中 $last\_ans$ 表示上一次询问操作的答案,如果不存在上一次询问操作则为 $0​$ 。

输出格式

对于每个询问操作,输出一行表示答案。

样例一

input

5 5 0
1 2
1 3
3 4
3 5
1 0 0 0 0
2 2 5
3 3
1 2 5 1
2 2 5
3 3

output

1
0
4
2

限制与约定

  • 对于所有数据,$1 \le n \le 10^5$ ,$1 \le m \le 10^5$ ,$-10^9 \le$ 点权 $\le 10^9$ ,
  • $subtask1(3pts):n,m \le 5000$ 。
  • $subtask2(10pts):$ 给定的树是一条链。
  • $subtask3(15pts):T=0$ ,且不存在操作 $3​$ 。
  • $subtask4(15pts):T=0$ 。
  • $subtask5(10pts):n,m \le 50000$ 。
  • $subtask6(47pts):$ 没有额外的限制。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载