UOJ Logo LFYZ Online Judge

LFYZOJ

#62. 普通树题

统计

作为一个普通树题,当然没有什么背景辣。

问题描述

你有一棵树,有 $n$ 个节点,标号 $1 \sim n$,点有点权。$1$ 为根,保证 $1$ 不会被删除。

有 $m$ 个操作,分为四种:

  • $\texttt{Query}\ x\ k$ 表示查询 $x$ 的子树内的第 $k$ 小。
  • $\texttt{Update}\ x\ v$ 表示将 $x$ 的权值改成 $v$。
  • $\texttt{Addnode}\ x\ v$ 表示在 $x$ 下接一个节点,权值为 $v$,编号为 $n+1$,然后 $n$ 增加 $1$。
  • $\texttt{Delnode}\ x$ 表示删除 $x$ 这个节点,保证 $x$ 为叶子。

输入格式

第一行,两个正整数 $n$ 和 $m$。

第二行,$n$ 个正整数 $A_i$,代表每个点的权值。

接下来 $n-1$ 行,每行两个正整数,代表一条边。

接下来 $m$ 行,每行一个操作,按照题目描述中的格式。

输出格式

对每个 Query 输出一行。

样例一

input

5 10
10 6 2 6 4 
2 1
3 2
4 2
5 3
Query 4 1
Query 1 1
Addnode 5 6
Addnode 4 10
Update 7 3
Delnode 7
Update 5 8
Query 5 2
Delnode 4
Addnode 6 6

output

6
2
8

数据范围与约定

对于 $20\%$ 的数据,$n \leq 100$,$m \leq 1000$。

对于 $50\%$ 的数据,不存在 AddnodeDelnode 操作。

对于 $70\%$ 的数据,$n \leq 5 \times 10^4$,$m \leq 10^5$。

对于 $100\%$ 的数据,$n \leq 10^5$,$m \leq 2\times 10^5$。

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

内存限制: $512\mathrm{MB}$

来源

玫葵之蝶 from JCYZ