OI Problems   关于

#aw66mn. The LCIS on the Tree

时间限制:1 s       空间限制:256 MiB       标签: 图论 树链剖分 重链剖分 数据结构 线段树 ICPC 成都 2013 

算法难度等级:0       思维难度等级:0       实现难度等级:0

本题来源于:2013 年 ACM-ICPC 中国成都省级编程大赛

给定一棵有 nn 个节点的树, 有 mm 次询问, 每次询问两点间的最短路径上的最长连续严格递增子序列。

For a sequence S1, S2, , SNS_1,\ S_2,\ \cdots,\ S_N, and a pair of integers (i, j)(i,\ j), if 1ijN1\leq i\leq j\leq N and Si<Si+1<Si+2<<Sj1<SjS_i < S_{i+1} < S_{i+2} < \cdots < S_{j-1} < Sj, then the sequence Si, Si+1, , SjS_i,\ S_{i+1},\ \cdots,\ S_j is a CIS (Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).

Now we consider a tree rooted at node 11. Nodes have values. We have QQ queries, each with two nodes uu and vv. You have to find the shortest path from uu to vv. And write down each nodes' value on the path, from uu to vv, inclusive. Then you will get a sequence, and please show us the length of its LCIS.


The first line has a number TT (T10T \leq 10), indicating the number of test cases.

For each test case, the first line is a number NN (N105N \leq 10^5), the number of nodes in the tree.

The second line comes with NN numbers v1, v2, v3, , vNv_1,\ v_2,\ v_3,\ \cdots,\ v_N, describing the value of node 11 to node NN. (1vi1091\leq v_i \leq 10^9)

The third line comes with N1N - 1 numbers p2, p3, p4, , pNp_2,\ p_3,\ p_4,\ \cdots,\ p_N, describing the father nodes of node 22 to node NN. Node 11 is the root and will have no father.

Then comes a number QQ, it is the number of queries. (Q105Q \leq 10^5)

For next QQ lines, each with two numbers uu and vv. As described above.


For test case XX, output Case #X: at the first line.

Then output QQ lines, each with an answer to the query.

There should be a blank line BETWEEN each test case.

1 2 3 4 5
1 1 3 3
1 5
4 5
2 5
Case #1: