#P9705. Escape from whk
Escape from whk
题目描述
给定一棵有 个结点的树,以 为根,并给定 的一个排列 。每次询问一个下标区间 。先取集合 ,再加入其中任意两点的最近公共祖先。求去重后的点数,即这个点集所张成的虚树的结点数。每次询问独立。
输入格式
第一行两个整数 。第二行有 个整数,第 个整数是结点 的父亲。第三行有 个整数 ,为一个排列。
接下来 行,每行两个整数 ,满足 。
输出格式
输出 行,每行一个整数,表示一次询问的答案。
样例
5 2
1 1 3 3
1 2 3 4 5
3 5
2 4
3
4
第一次取 ,无需新增结点。第二次取 ,还要加入根 。
数据范围
。
对于 20% 的数据,。对于 40% 的数据,。另外 10% 的数据保证树为一条链,另外 20% 的数据保证各询问的区间长度之和不超过 。