QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 500 MB Total points: 100

# 7471. ODT

统计

题目描述

给你一棵树,边权为 $1$,有点权。

需要支持两个操作:

  • 1 x y z:表示把树上 $x$ 到 $y$ 这条简单路径的所有点点权都加上 $z$。
  • 2 x y:表示查询与点 $x$ 距离小于等于 $1$ 的所有点里面的第 $y$ 小点权。

输入格式

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

第二行 $n$ 个整数表示每个点的点权。

之后 $n-1$ 行,每行两个整数 $x,y$ 表示 $x$ 和 $y$ 之间连有一条边。

之后 $m$ 行,每行为 1 x y z 或者 2 x y 形式,意义如上述。

输出格式

对每个 2 操作输出一行,每行一个整数表示答案。

数据保证每次询问都存在答案。

样例 #1

样例输入 #1

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

样例输出 #1

4
3
4

提示

Idea:nzhtl1477,

Solution:nzhtl1477( $O( n\log^2n/ \log\log n )$ solution ),negiizhao( $O( n\log n\log\log\log n )$ solution ),ccz181078( $O( n\log n )$ solution ),

Code:nzhtl1477( $O( n\log^2 n/ \log\log n )$ code )

Data:nzhtl1477( partially uploaded )

subtask 1:$20\%$ $n,m\leq 1000$。

subtask 2:$10\%$ 树为一条链。

subtask 3:$20\%$ $n,m\leq 10^5$。

subtask 4:$30\%$ $n,m\leq 4\times 10^5$。

subtask 5:$20\%$ $n,m\leq 10^6$。

对于 $100\%$ 的数据,$1\leq n,m\leq 10^6$,$0\leq $ 每次加的数 $\leq 2000$,$0\leq $ 初始的点权 $\leq 2000$。