题目描述
Description
你有两棵有根树，每棵各有n 个顶点。让我们用整数1到n给每棵树的顶点编号。两棵树的根都是顶点1。第一棵树的边都染成蓝色，第二棵树的边都染成红色。简明起见，我们称第一棵树是蓝色的，以及第二棵树是红色的。
同时满足下面的两个条件下，边(x, y) 有害于边(p,q)：
1. 边(x,y)的颜色不同于边(p,q)。
2. 考虑与边(p, q) 颜色相同的树，编号为x, y 的两个顶点中恰好有且只有一个同时在顶点p 的子树与顶点q 的子树里。
在这个问题里，你的任务是模拟下述过程。此过程由若干阶段组成：
1. 在同一个阶段中删除的边颜色相同。
2. 在第一阶段，删除恰好一条蓝色的边。
3. 假设在阶段i 我们删去了边(u1，v1)， (u2，v2)，... ， (uk，vk)。那么在阶段i+1我们要删去有害于(u1，v1) 的边，然后删去有害于(u2，v2) 的边，接着继续删到删完有害于(uk，vk) 的边。
对于每个阶段，求解哪些边将在这个阶段中被删除。注意，有害边的定义只依赖于开始删边之前的初始就拥有的两棵有根树。
Input
输入第一行为整数n（2<=n<=2*10^5）——两棵树分别有的顶点数目。
接下来的一行包含n-1个正整数a2,a3,...,an(1<=ai<=n;ai<>i)，描述第一棵树的边。数字ai意味着第一棵树有一条边连接顶点ai和顶点i。
接下来的又一行包含n-1个正整数b2,b3,...,bn(1<=bi<=n;bi<>i)，描述第二棵树的边。数字ai意味着第二棵树有一条边连接顶点bi和顶点i。
接下来的再一行包含一个整数idx（1 <=idx < n）表示在第一阶段中删除的边的编号。我们让每棵树的每条边按照他们在输入中的前后顺序从1 到n-1 编号。
Output
对于每个阶段输出两行。如果这个阶段删除的边是蓝色的，那么对应这一阶段的两行中，第一行必须为单词Blue，否则为单词Red。对应的第二行包含所有此阶段删除的边的编号，按数字递增顺序输出。
Sample Input
5
1 1 1 1
4 2 1 1
3
Sample Output
Blue
3
Red
1 3
Blue
1 2
Red
2
Data Constraint
30% 的数据，n<=100。
60% 的数据，n<=1000。
简明起见，我们假设有根树中的边都是有向的，并且从顶点1 可以到达所有顶点。那么，顶点v 的子树就是顶点v (在前面得到的有向图中)能到达的点组成的点集（顶点v 也包括在这个集合中）。
题解
好像有树套树的神奇做法？但是一个log都会被卡
一条路径u-v经过一条边x-y(fa[y]=x)，等价与子树y内只有一个该路径中的端点，即
min(bg[u],bg[v])<bg[y],bg[y]<=max(bg[u],bg[v])<=ed[y]
或
bg[y]<=min(bg[u],bg[v])<=ed[y],ed[y]<max(bg[u],bg[v])
所以对两棵树分别搞出bg和ed，把一条边挂在另一棵树上
把边按bg[y]从小到大/按bg[x]从大到小排序，然后按bg[x]/bg[y]为关键字插在线段树里，按顺序用vector存
那么一次要删掉的边只能是不在[x,y]区间里的，所以从后往前删即可
一个小优化：
如果把[u,v]（u为关键字）插到区间[l,r]里，则必须保证v不在[l,r]里，否则没有意义
因为查找的区间[x,y]必然包含[l,r]，若v在[l,r]里则必在[x,y]中，那么v不会被删掉
code
c++的优越性
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define fout
using namespace std;
bool bz[2][200001];
int n,i,j,k,l,x,y,h,t,I;
struct type{
int x,y,id;
} b[200001],c[200001];
bool cmp1(type a,type b) {return a.y<b.y;};
bool cmp2(type a,type b) {return a.x>b.x;};
struct Type{
int x,y;
} d[400001];
bool Cmp(Type a,Type b) {return a.y<b.y;}
void del(int I,int x)
{
if (!bz[I][x])
{
bz[I][x]=1;
++t;
d[t]={I,x};
}
}
int get()
{
char ch=getchar();
int x=0;
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();
return x;
}
struct xdtree{
vector<int> tr[800001];
int I;
void change(int t,int l,int r,int x,int s,int id)
{
int mid=(l+r)/2;
if (!(l<=s && s<=r))
{
tr[t].push_back(s);
tr[t].push_back(id);
}
if (l==r) return;
if (x<=mid)
change(t*2,l,mid,x,s,id);
else
change(t*2+1,mid+1,r,x,s,id);
}
void find(int t,int l,int r,int x,int y)
{
int mid=(l+r)/2;
if (x<=l && r<=y)
{
while (!tr[t].empty())
{
int l=tr[t].size()-2,s=tr[t][l],id=tr[t][l+1];
if (!(x<=s && s<=y))
del(I^1,id),tr[t].pop_back(),tr[t].pop_back();
else
break;
}
return;
}
if (x<=mid)
find(t*2,l,mid,x,y);
if (mid<y)
find(t*2+1,mid+1,r,x,y);
}
};
struct tree{
int A[200001][2];
int a[400002][2];
int ls[200001];
int bg[200001];
int ed[200001];
int fa[200001];
int len=1,tot=0;
int I;
xdtree t1,t2;
void New(int x,int y)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
ls[x]=len;
}
void dfs(int Fa,int t)
{
int i;
fa[t]=Fa;
bg[t]=++tot;
for (i=ls[t]; i; i=a[i][1])
if (a[i][0]!=Fa)
dfs(t,a[i][0]);
ed[t]=tot;
}
void init()
{
int i,j;
t1.I=t2.I=I;
fo(i,2,n)
{
j=get();
A[i-1][0]=i;
A[i-1][1]=j;
New(j,i);New(i,j);
}
dfs(0,1);
}
} a[2]; //a[0]=blue a[1]=red
void swap(int &x,int &y)
{
int z=x;
x=y;
y=z;
}
int main()
{
freopen("tree.in","r",stdin);
#ifdef fout
freopen("tree.out","w",stdout);
#endif
n=get();
a[0].I=0;a[1].I=1;
a[0].init();
a[1].init();
fo(I,0,1)
{
fo(i,1,n-1)
{
x=a[I^1].bg[a[I].A[i][0]];
y=a[I^1].bg[a[I].A[i][1]];
if (x>y) swap(x,y);
b[i]={x,y,i};
c[i]={x,y,i};
}
sort(b+1,b+(n-1)+1,cmp1);
sort(c+1,c+(n-1)+1,cmp2);
fo(i,1,n-1)
{
a[I^1].t1.change(1,1,n,b[i].x,b[i].y,b[i].id);
a[I^1].t2.change(1,1,n,c[i].y,c[i].x,c[i].id);
}
}
x=get();
h=0;t=1;
d[1]={0,x};
bz[0][x]=1;
while (h<t)
{
++h;
x=a[d[h].x].A[d[h].y][0];
y=a[d[h].x].A[d[h].y][1];
if (a[d[h].x].fa[x]==y) swap(x,y);
a[d[h].x].t1.find(1,1,n,a[d[h].x].bg[y],a[d[h].x].ed[y]);
a[d[h].x].t2.find(1,1,n,a[d[h].x].bg[y],a[d[h].x].ed[y]);
}
l=0;
fo(i,1,t)
if (i==t || d[i].x!=d[i+1].x)
{
sort(d+(l+1),d+i+1,Cmp);
printf(d[i].x==0?"Blue
":"Red
");
fo(j,l+1,i)
printf("%d ",d[j].y);
printf("
");
l=i;
}
fclose(stdin);
fclose(stdout);
return 0;
}