题目
有点长就不说了。
思考历程
强行刚出了一个(O(n lg^2 n))的做法，被卡了。
先将(dfs)序求出来，一个子树对应着一段区间。
用树上差分的思想来搞，维护区间里每条边的出现次数。
树状数组套线段树来搞。
由于直接树套树空间会被卡，所以在预处理的时候用可持久化线段树合并的方式来进行，空间复杂度是(O(n lg n))的。
修改的时候直接将与某条边所有相关的信息抹掉，于是就可以暴力改。时间是(O(lg^2 n))的（然而这是最花时间的操作）。
这个打了5000+的做法到最后没有AC……
2333333333……
正解
正解真的是太简单了。
首先也是将(dfs序)求出来，记(in_x)和(out_x)分别表示(x)的子树在(dfs)序上的左右端点。
对于每条边，钦定(in_u<in_v)。
对于一个子树，分(u)在子树内(v)不在子树内和(v)在子树内(u)不在子树内的情况。
那就维护两棵线段树，每个节点维护一个线性表（什么链表或vector之类的）。
一开始将边按照(in_v)或(in_u)排序，然后插入线段树中对应的位置里。
在删边的时候找出线段树上的区间，在这些区间中的线性表中单调地删。
显然线性表的大小为(O(nlg n))，然后就能过去了……
非常好打……
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#define N 200010
int n,T;
struct EDGE{
int to;
EDGE *las;
} e[N*4+N*20*2*2];
int ne;
EDGE *last[2][N];
struct edge{
int u,v;
} ed[2][N];
int in[2][N],out[2][N],nowdfn;
void init(int x,int fa){
in[T][x]=++nowdfn;
for (EDGE *ei=last[T][x];ei;ei=ei->las)
if (ei->to!=fa)
init(ei->to,x);
out[T][x]=nowdfn;
}
int q[N];
bool cmp1(int x,int y){return in[T][ed[!T][x].v]<in[T][ed[!T][y].v];}
bool cmp2(int x,int y){return in[T][ed[!T][x].u]>in[T][ed[!T][y].u];}
EDGE *d1[2][N*4],*d2[2][N*4];
void insert1(int k,int l,int r,int p){
e[ne]={p,d1[T][k]};
d1[T][k]=e+ne++;
if (l==r)
return;
int mid=l+r>>1;
if (in[T][ed[!T][p].u]<=mid)
insert1(k<<1,l,mid,p);
else
insert1(k<<1|1,mid+1,r,p);
}
void insert2(int k,int l,int r,int p){
e[ne]={p,d2[T][k]};
d2[T][k]=e+ne++;
if (l==r)
return;
int mid=l+r>>1;
if (in[T][ed[!T][p].v]<=mid)
insert2(k<<1,l,mid,p);
else
insert2(k<<1|1,mid+1,r,p);
}
bool killed[2][N];
int ans[2][N*20*2],*now,*old,kn,ko;
void kill(int k,int l,int r,int x){
if (in[T][x]<=l && r<=out[T][x]){
while (d1[T][k] && in[T][ed[!T][d1[T][k]->to].v]>out[T][x]){
now[++kn]=d1[T][k]->to;
d1[T][k]=d1[T][k]->las;
}
while (d2[T][k] && in[T][ed[!T][d2[T][k]->to].u]<in[T][x]){
now[++kn]=d2[T][k]->to;
d2[T][k]=d2[T][k]->las;
}
return;
}
int mid=l+r>>1;
if (in[T][x]<=mid)
kill(k<<1,l,mid,x);
if (mid<out[T][x])
kill(k<<1|1,mid+1,r,x);
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
for (T=0;T<=1;++T){
for (int i=2;i<=n;++i){
int x;
scanf("%d",&x);
e[ne]={x,last[T][i]};
last[T][i]=e+ne++;
e[ne]={i,last[T][x]};
last[T][x]=e+ne++;
ed[T][i-1]={x,i};
}
nowdfn=0;
init(1,0);
}
for (T=0;T<=1;++T){
for (int i=1;i<n;++i)
if (in[T][ed[!T][i].u]>in[T][ed[!T][i].v])
swap(ed[!T][i].u,ed[!T][i].v);
for (int i=1;i<n;++i)
q[i]=i;
sort(q+1,q+n,cmp1);
for (int i=1;i<n;++i)
insert1(1,1,n,q[i]);
sort(q+1,q+n,cmp2);
for (int i=1;i<n;++i)
insert2(1,1,n,q[i]);
}
now=ans[0],old=ans[1];
scanf("%d",&now[kn=1]);
printf("Blue
%d
",now[1]);
killed[0][now[1]]=1;
for (T=0;1;T^=1){
swap(now,old),swap(kn,ko);
kn=0;
for (int i=1;i<=ko;++i){
int u=ed[T][old[i]].u,v=ed[T][old[i]].v,x=in[T][u]>in[T][v]?u:v;
kill(1,1,n,x);
}
for (int i=1;i<=kn;++i)
if (killed[!T][now[i]]){
swap(now[i],now[kn]),kn--;
--i;
}
else
killed[!T][now[i]]=1;
if (kn==0)
break;
if (T==0)
printf("Red
");
else
printf("Blue
");
sort(now+1,now+kn+1);
for (int i=1;i<=kn;++i)
if (now[i]!=now[i-1])
printf("%d ",now[i]);
putchar('
');
}
return 0;
}
总结
要善于估计一下时间复杂度。
比如看到(n=2e5)就知道是要卡的。