题意：给出一棵初始所有边都是蓝边的树，每次选一条所有边都是蓝边的简单路径，将路径上一条蓝边断开，在路径两端连一条红边，问是否可以转变成规定的所有边都是红边的树。
将红树的每条边视为蓝树上一条路径，每次找一条蓝树上只被一条路径覆盖的边，把这条路径删掉。如果找不到，那么无解
可以用树剖+线段树+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;
}