题目描述

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\n":"Red\n");
        fo(j,l+1,i)
        printf("%d ",d[j].y);
        printf("\n");
        
        l=i;
    }
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}

3722. Two Rooted Trees

原文：https://www.cnblogs.com/gmh77/p/12134527.html