34 - 树的基本信息

已知一颗n个节点的树,根节点为1,且根节点的深度为1.

JM有q次查询,每次以下信息种的一个

  • opt = 1,表示查询x节点的深度
  • opt = 2,表示查询x节点的父亲节点编号
  • opt = 3,表示查询x节点到根节点的距离、
  • opt = 4,表示查询以x节点为根的子树大小
  • opt = 5,表示查询以x节点为根的子树权值和
  • opt = 6,表示查询以x节点为根的子树中所有权值的最大值

输入

输入第一行包含两个整数n,q,表示树的节点个数,以及查询的个数。

接下来输入一行n个整数,对应每一个节点的权值a_i

接下来输入n-1行,每行输入三个整数u,v,w,表示节点u,v之间有一条长度为w的边。

接下来输入q行,每行输入两个整数opt,x,表示查询x节点对应的opt类型的查询值

输出

输出q行,表示每一次查询对应的结果

注意,如果查询根节点的父亲,则输出0

样例

输入

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

输出

3
1
6
1
15
5

提示

数据规模

10<=n<=10^3, -1000<=a_i <= 1000

10 <= q <= 6 * 10^3, 1 <= w <= 1000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题