#P9705. Escape from whk

    ID: 6324 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-虚树补充相邻点 LCA回滚莫队链表回滚维护状态增量维护欧拉序ST 表

Escape from whk

题目描述

给定一棵有 nn 个结点的树,以 11 为根,并给定 1,…,n1,\ldots,n 的一个排列 aa。每次询问一个下标区间 [l,r][l,r]。先取集合 {al,…,ar}\{a_l,\ldots,a_r\},再加入其中任意两点的最近公共祖先。求去重后的点数,即这个点集所张成的虚树的结点数。每次询问独立。

输入格式

第一行两个整数 n,mn,m。第二行有 n−1n-1 个整数,第 ii 个整数是结点 i+1i+1 的父亲。第三行有 nn 个整数 a1,…,ana_1,\ldots,a_n,为一个排列。

接下来 mm 行,每行两个整数 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n。

输出格式

输出 mm 行,每行一个整数,表示一次询问的答案。

样例

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

第一次取 3,4,53,4,5,无需新增结点。第二次取 2,3,42,3,4,还要加入根 11。

数据范围

1≤n,m≤500001\le n,m\le50000。

对于 20% 的数据,n,m≤100n,m\le100。对于 40% 的数据,n,m≤20000n,m\le20000。另外 10% 的数据保证树为一条链,另外 20% 的数据保证各询问的区间长度之和不超过 5×1065\times10^6。

原题面 PDF