/ SUOI / 题库 /

#32 最近公共祖先三

#32 最近公共祖先三

背景

SBW和LYH被SML送进了一棵树,并且被丢在不同的节点上
SBW希望找到LYH
通过XY宏,SBW可以确定一些节点是LYH可能出现的位置
SBW希望求出这些点的最近公共祖先,以便找到LYH

描述

给出一棵N个点以1为根的树和一个1至N的排列
M个询问,每次询问排列中l至r那些点的最近公共祖先

输入

第一行两个整数N,M
第二行N个整数,为1至N的一个排列
接下来N-1行,每行两个整数x,y表示树上x与y之间有边
接下来M行,每行两个整数l,r

输出

M行,每行一个整数,为对应询问的答案

样例

输入

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

输出

5
3
1
2
1

范围

40% N,M<=10
70% N<=3000 M<=700
100% 1<=N<=300000 1<=M<=500000 1<=x,y<=N 1<=l<=r<=N

限制

2000ms
256M

信息

难度
2
分类
(无)
标签
(无)
递交数
3
已通过
2
通过率
67%
上传者