难度&推荐指数：
- 思维难度：提高+/省选-
- 实现难度：提高+/省选-
- 推荐指数：8.0（推荐指数最高为10.0）
题目翻译
Trees of Tranquillity
宁静的树
Soroush and Keshi each have a labeled and rooted tree on $n$ vertices. Both of their trees are rooted from vertex $ 1 $ .
Soroush 和 Keshi 都有一个做了标记的有着 $ n $ 个节点的有根树。这两颗树都以节点 $ 1 $ 为根。
Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on $ n $ vertices.
Soroush 和 Keshi 曾经进行过激烈的竞争。在竞争的最后时期，他们成为了同盟来一起准备 Codeforces 比赛。为了庆祝这个幸运时刻，他们决定制作一个有 $ n $ 个节点的纪念图。
They add an edge between vertices $ u $ and $ v $ in the memorial graph if both of the following conditions hold:
- One of $ u $ or $ v $ is the ancestor of the other in Soroush's tree.
- Neither of $ u $ or $ v $ is the ancestor of the other in Keshi's tree.
当两个点 $ u $ 和 $ v $ 满足以下条件时，它们在纪念图上面有一条边。
- 在 Soroush 的树上 $ u $ 是 $ v $ 的祖先或者 $ v $ 是 $ u $ 的祖先。
- 在 Keshi 的树上 $ u $ 和 $ v $ 都不是对方的祖先。
Here vertex $ u $ is considered ancestor of vertex $ v $, if $ u $ lies on the path from $ 1 $ (the root) to the $ v $.
如果 $ u $ 是 $ v $ 的祖先，则 $ u $ 在 $ v $ 到根节点的最短路径上。
Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big.
不知从哪里冒出来的 Mashtali 想要在这个纪念图中找到最大的派系。
Help Mashtali by finding the size of the maximum clique in the memorial graph.
帮助 Mashtali 找到这个最大派系的节点数吧！
As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.
提示：派系是一个图的子集，在派系中，任意两点之间都有一条边。
题解
算法：dfs
数据结构：平衡树（可用 std::set 代替）
下文中 Soroush 的树简称 st ，Keshi 的树简称 kt 。
不难发现，在题目要求的派系中的任意两点 $ u,v $ ，总满足在 st 中一者是另一者的祖先，且在kt中没有祖先关系。
同时不难发现，这个派系中的点，必然是 st 的一条从根到叶子的树链的子集。
那么我们可以先忽略时间复杂度，枚举 st 的每一条从根到叶子的树链看看有没有办法来找到题目要求的派系。我们先假设这个树链上所有的点都在派系中，然后再想办法删除一些点。可以发现，如果存在一个点 $ u $ 在 kt 中是 $ v $ 的祖先（$ u,v $ 均是被选定的树链中的节点），那么删除 $ u $ 总是比删除 $ v $ 要优。因为如果要删除 $ v $ 有可能还要删除其他以 $ u $ 为祖先的节点，而删除 $ u $ 就不用删除以它为祖先的其它节点。所以我们可以发现，对于选定的一条树链，我们只需要删除所有在 kt 中为其它节点祖先的点即可。
如何判断一个节点是否是另一个节点的祖先呢？ 可以考虑使用 dfs 序。我们以 in[i] 代表 $i$ 节点在刚进入 dfs 时的 dfs 序，以 out[i] 代表 $i$ 节点在出 dfs 时的 dfs 序。
void dfs(int i)
{
in[i]=++dfn;
dfni[dfn]=i;
for(int p=V[i].eh;p;p=E[p].next)
{
dfs_kt(E[p].to);
}
out[i]=dfn;
}那么如果 $ u $ 为 $ v $ 的祖先，当且仅当 in[u]<in[v] && out[u]>=out[v] .
接下来考虑枚举 st 上单一树链是如何处理树链上的点。我们可以从根节点挨个把树链上的点加入派系集合，当添加 $ i $ 节点时，如果存在 $ i $ 节点的祖先，则删除其祖先并加入 $ i $ 节点；如果 $ i $ 节点是已添加的别的节点的祖先，则不添加 $ i $ 节点；如果上面两点都不满足，则直接添加 $ i $ 节点。最后看看能添加多少个节点就是这个树链的答案。
在添加 $ i $ 节点时，派系集合中最多只能存在一个 $ i $ 节点的祖先。如果这个祖先存在，我们设它为 $ u $ ，则 in[u] 在集合中是 in[i] 的前驱。虽然说派系集合中可能存在多个以 $ i $ 为祖先的节点，但是如果存在，则 in[i] 在集合中的后继一定是以 $ i $ 为祖先的节点。那么用一棵平衡树维护即可。
怎么把链的情况扩展到树呢？我们可以利用回溯算法，每个节点遍历结束后将其对集合的修改“撤销”，就可以实现扩展的到树的情况。
时间复杂度：$ O(n\log n) $
代码（使用非旋式Treap实现）：
#pragma GCC optimize ("O2")
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define MAXN 300005
#define lc nodes[i].ch[0]
#define rc nodes[i].ch[1]
struct treap{
struct node{
int v;
int rnd;
int ch[2];
int siz;
}nodes[MAXN*2];
int tot=0,root=0;
void init()
{
tot=0;
root=0;
}
void pushup(int i)
{
nodes[i].siz=nodes[lc].siz+nodes[rc].siz+1;
}
int new_node(int v)
{
int i=++tot;
nodes[i].v=v;
nodes[i].rnd=rand();
nodes[i].siz=1;
lc=rc=0;
return i;
}
void split(int i,int v,int& x,int& y)
{
if(!i) x=y=0;
else
{
if(nodes[i].v<=v) split(rc,v,rc,y),x=i;
else split(lc,v,x,lc),y=i;
pushup(i);
}
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int i;
if(nodes[x].rnd>nodes[y].rnd)
{
i=x;
rc=merge(rc,y);
}
else
{
i=y;
lc=merge(x,lc);
}
pushup(i);
return i;
}
void insert(int v)
{
int x,y;
split(root,v,x,y);
root=merge(merge(x,new_node(v)),y);
}
void remove(int v)
{
int i,x,y;
split(root,v,x,y);
split(x,v-1,x,i);
i=merge(lc,rc);
root=merge(merge(x,i),y);
}
int find_pre(int v)
{
int x,y,i,ans;
split(root,v-1,x,y);
i=x;
while(rc) i=rc;
ans=nodes[i].v;
root=merge(x,y);
return ans;
}
int find_next(int v)
{
int x,y,i,ans;
split(root,v,x,y);
i=y;
while(lc) i=lc;
ans=nodes[i].v;
root=merge(x,y);
return ans;
}
int size()
{
return nodes[root].siz;
}
}t;
struct tree{
struct node{
int eh;
}V[MAXN];
struct edge{
int to;
int next;
}E[MAXN];
int tot;
void add_edge(int from,int to)
{
E[++tot]=(edge){to,V[from].eh};
V[from].eh=tot;
}
void init(int n)
{
tot=0;
memset(V+1,0,sizeof(node)*n);
//注意这里不能初始化整个数组，不然会超时
}
}st,kt;
int in[MAXN],out[MAXN];
int dfn;
int dfni[MAXN];
void dfs_kt(int i)
{
auto& E=kt.E;
auto& V=kt.V;
in[i]=++dfn;
dfni[dfn]=i;
for(int p=V[i].eh;p;p=E[p].next)
{
dfs_kt(E[p].to);
}
out[i]=dfn;
}
int ans;
void dfs_st(int i)
{
auto& E=st.E;
auto& V=st.V;
int j=dfni[t.find_next(in[i])],tmp=0;
bool flag=false;
if(!(j&&out[i]>=out[j]))
{
flag=true;
t.insert(in[i]);
j=dfni[t.find_pre(in[i])];
if(j&&out[j]>=out[i])
{
tmp=in[j];
t.remove(in[j]);
}
}
if(t.size()>ans) ans=t.size();
for(int p=V[i].eh;p;p=E[p].next)
{
dfs_st(E[p].to);
}
if(flag) t.remove(in[i]);
if(tmp) t.insert(tmp);
}
int main()
{
srand((unsigned)time(NULL));
int T,n,i,tmp;
scanf("%d",&T);
while(T--)
{
//initialize
scanf("%d",&n);
st.init(n);
kt.init(n);
t.init();
dfn=0;
ans=0;
//input
for(i=2;i<=n;i++)
{
scanf("%d",&tmp);
st.add_edge(tmp,i);
}
for(i=2;i<=n;i++)
{
scanf("%d",&tmp);
kt.add_edge(tmp,i);
}
//solve
dfs_kt(1);
dfs_st(1);
//output
printf("%d\n",ans);
}
return 0;
}