居然自己想出了 AGC E。
首先考虑删边再加红边的本质是什么。容易发现，如果一条目标树上的边当前还没有被加上，且这条边所连两点在原树上的路径被切断，则此时一定无解。因为不管怎么加删边，这都是一棵树，而此时两点路径上一定有红边。
所以，我们就可以得到此时可以新增一条边 \((u,v)\) 的条件：路径上存在一条边，没有一条没有新增过的目标树上的边 \((u',v')\)，使得原树上 \((u',v')\) 的路径不经过改变。容易发现，这等同于在原树上把所有 \((u,v)\) 路径上边的边权 \(+1\)，查询路径上有没有边权为 \(1\) 的边。简单树剖维护即可。
作者在写的时候降智了，找到对应 \((u,v)\) 时没有想到维护编号和，于是在 SGT 上每个点用了个 set 维护区间内有的编号，时空复杂度 \(O(n\log^3n)\)。其实可以 \(O(n\log^2n)\)。但是常数小，无所谓了（bushi）。
code：
点击查看代码
int n,m;
int dep[N],fa[N],siz[N],son[N];
int cur,top[N],dfn[N];
int tr[N<<2],tag[N<<2];
int tot,head[N];
struct node{
int to,nxt;
}e[N<<1];
pii d[N];
set<int> st[N<<2],E;
inline void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
go(i,u){
int v=e[i].to;
if(v==f)
continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
dfn[u]=++cur;
if(!son[u])
return;
dfs2(son[u],t);
go(i,u){
int v=e[i].to;
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
inline void pushup(int o){
tr[o]=min(tr[o<<1],tr[o<<1|1]);
}
inline void reset(int l,int r,int o,int k){
tr[o]+=k;
tag[o]+=k;
}
inline void pushdown(int l,int r,int o){
int mid=(l+r)>>1;
reset(l,mid,o<<1,tag[o]);
reset(mid+1,r,o<<1|1,tag[o]);
tag[o]=0;
}
void update(int l,int r,int o,int x,int y,int k,int op){
if(l>=x&&r<=y){
if(op){
st[o].insert(k);
reset(l,r,o,1);
}else{
st[o].erase(k);
reset(l,r,o,-1);
}
return;
}
pushdown(l,r,o);
int mid=(l+r)>>1;
if(x<=mid)
update(l,mid,o<<1,x,y,k,op);
if(y>mid)
update(mid+1,r,o<<1|1,x,y,k,op);
pushup(o);
}
int query(int l,int r,int o){
if(st[o].size())
return *st[o].begin();
pushdown(l,r,o);
int mid=(l+r)>>1;
if(tr[o<<1]<tr[o<<1|1])
return query(l,mid,o<<1);
return query(mid+1,r,o<<1|1);
}
void change(int l,int r,int o){
if(l==r){
tr[o]=inf;
return;
}
change(l,(l+r)>>1,o<<1);
pushup(o);
}
void work(int l,int r,int o){
if(l==r){
tr[o]=inf;
return;
}
pushdown(l,r,o);
int mid=(l+r)>>1;
if(tr[o<<1]<tr[o<<1|1])
work(l,mid,o<<1);
else
work(mid+1,r,o<<1|1);
pushup(o);
}
void modify(int u,int v,int k,int op){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])
swap(u,v);
update(1,n,1,dfn[top[u]],dfn[u],k,op);
u=fa[top[u]];
}
if(dfn[u]>dfn[v])
swap(u,v);
if(dfn[u]<dfn[v])
update(1,n,1,dfn[u]+1,dfn[v],k,op);
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n-1){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1,1);
rep(i,1,n-1){
scanf("%d%d",&d[i].fi,&d[i].se);
modify(d[i].fi,d[i].se,i,1);
}
change(1,n,1);
rep(i,1,n-1){
E.clear();
if(tr[1]>1){
puts("NO");
return;
}
int p=query(1,n,1);
modify(d[p].fi,d[p].se,p,0);
while(!tr[1])
work(1,n,1);
}
puts("YES");
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}