agc014e

题意：给出一棵初始所有边都是蓝边的树，每次选一条所有边都是蓝边的简单路径，将路径上一条蓝边断开，在路径两端连一条红边，问是否可以转变成规定的所有边都是红边的树。

将红树的每条边视为蓝树上一条路径，每次找一条蓝树上只被一条路径覆盖的边，把这条路径删掉。如果找不到，那么无解
可以用树剖+线段树+set维护，线段树维护两个标记表示子树中是否有被覆盖一次和零次的边。标记永久化
复杂度$$O(nlog^3n)$$

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define ls l,mid,now<<1
#define rs mid+1,r,now<<1|1
int n,tot,cnt,ret;
int head[N],nex[N<<1],to[N<<1];
int deep[N],fa[N],son[N],size[N],top[N],pos[N],bel[N];
int X[N],Y[N],num[N<<2],v0[N<<2],v1[N<<2];
set<int>se[N<<2];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs1(int x,int y)
{
    size[x]=1;
    fa[x]=y;deep[x]=deep[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs1(to[i],x);
            size[x]+=size[to[i]];
            son[x]=size[to[i]]>size[son[x]] ? to[i] : son[x]; 
        }
}
void dfs2(int x,int y,int tp)
{
    top[x]=tp;
    pos[x]=++cnt;bel[cnt]=x;
    if(son[x])dfs2(son[x],x,tp);
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y&&to[i]!=son[x])
            dfs2(to[i],x,to[i]);
}
void pushup(int l,int r,int now)
{
    if(l==r)
    {
        v0[now]=(num[now]==0);
        v1[now]=(num[now]==1);
        return;
    }
    if(num[now]==0)v0[now]=v0[now<<1]|v0[now<<1|1];
    else v0[now]=0;

    if(num[now]==0)v1[now]=v1[now<<1]|v1[now<<1|1];
    else if(num[now]==1)v1[now]=v0[now<<1]|v0[now<<1|1];
    else v1[now]=0;
}
void insert(int l,int r,int now,int lq,int rq,int p)
{
    if(lq<=l&&r<=rq)
    {
        se[now].insert(p);
        num[now]++;
        pushup(l,r,now);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=lq)insert(ls,lq,rq,p);
    if(mid<rq) insert(rs,lq,rq,p);
    pushup(l,r,now);
}
void mark(int x,int y,int p)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        insert(1,n,1,pos[top[x]],pos[x],p);
        x=fa[top[x]];
    }
    if(x!=y)
    {
        if(deep[x]<deep[y])swap(x,y);
        insert(1,n,1,pos[y]+1,pos[x],p);
    }
}
void update(int l,int r,int now,int v)
{
    if(num[now])
    {
        ret=*(se[now].begin());
        v=0;
    }
    if(l==r)return;
    int mid=(l+r)>>1;
    if((v==0&&v0[now<<1])||(v==1&&v1[now<<1]))
        update(ls,v);
    else update(rs,v);
}
void del(int l,int r,int now,int lq,int rq,int p)
{
    if(lq<=l&&r<=rq)
    {
        se[now].erase(p);
        num[now]--;
        pushup(l,r,now);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=lq)del(ls,lq,rq,p);
    if(mid<rq) del(rs,lq,rq,p);
    pushup(l,r,now);    
}
void del(int x,int y,int p)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        del(1,n,1,pos[top[x]],pos[x],p);
        x=fa[top[x]];
    }
    if(x!=y)
    {
        if(deep[x]<deep[y])swap(x,y);
        del(1,n,1,pos[y]+1,pos[x],p);
    }   
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(int i=1;i<=n<<2;i++)v0[i]=1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&X[i],&Y[i]);
        mark(X[i],Y[i],i);
    }
    for(int i=1;i<n;i++)
    {
        if(!v1[1])return puts("NO"),0;
        update(1,n,1,1);
        del(X[ret],Y[ret],ret);
    }
    puts("YES");
    return 0;
}