传送门

其实就是要找一个删边的顺序,使得每次删边之后两边联通块之间只有一条目标的边连着。这里每条目标边可以看成原树上的一条路径。那就直接树剖建线段树,然后对所有目标边在两个端点之间的路径上每条边+1就行了。每次要删边的时候,就找一条当前为1的边,如果找不到就无解,否则就把这条边删了,并且把贡献出这个1的目标边在原树上的路径每条边-1。可以证明这样做一定是对的。(大概就是每条目标边的路径里面最多只会同时存在一条边是1,然后路径里没有共同边的目标边不会互相影响)

考虑怎么找到贡献这个1的目标边。我没想到1个log的做法,直接暴力树套树做的。不知道正解是不是1个log做,也懒得看题解了。。。(然而如果1个log的话就要写lct了)

写的时候全程失智,有一堆细节没考虑(其实也不是细节,都是很明显的地方,只是我比较傻逼),导致调了很久。

代码:

#include <cstdio>
#include <cstring>
#include <cassert>
#include <set>
#include <algorithm>
#define MAXN 200010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,sizew;
int g[MAXN],nume;
int size[MAXN],son[MAXN],dep[MAXN],pre[MAXN],top[MAXN];
int w[MAXN][2],numw,pt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    size[x]=1; son[x]=0;
    pre[x]=p;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dep[e[i].to]=dep[x]+1;
            dfs(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
        }
}

void dfs2(int x,int p){
    pt[w[x][0]=++numw]=x;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && e[i].to!=son[x]){
            top[e[i].to]=e[i].to;
            dfs2(e[i].to,x);
        }
    w[x][1]=numw;
}

namespace Gao1{
    struct node{
        int tag,minv;
    }a[MAXN<<2];

    void pushdown(int x){
        if(a[x].tag){
            a[x<<1].tag+=a[x].tag;
            a[x<<1].minv+=a[x].tag;
            a[x<<1|1].tag+=a[x].tag;
            a[x<<1|1].minv+=a[x].tag;
            a[x].tag=0;
        }
    }

    void add(int x,int l,int r,int cl,int cr,int v){
        if(l<=cl && cr<=r){
            a[x].tag+=v;
            a[x].minv+=v;
            return;
        }
        pushdown(x);
        int mid=(cl+cr)>>1;
        if(l<=mid) add(x<<1,l,r,cl,mid,v);
        if(r>mid) add(x<<1|1,l,r,mid+1,cr,v);
        a[x].minv=min(a[x<<1].minv,a[x<<1|1].minv);
    }

    int find(int x,int cl,int cr){
        if(cl==cr) return cl;
        int mid=(cl+cr)>>1;
        pushdown(x);
        if(a[x<<1].minv==1) return find(x<<1,cl,mid);
        else return find(x<<1|1,mid+1,cr);
    }

    void init(){
        for(int i=1;i<=sizew;i++)
            if(i>=2 && i<=n) a[sizew+i-1].minv=0;
            else a[sizew+i-1].minv=2;
        for(int i=sizew-1;i;i--)
            a[i].minv=min(a[i<<1].minv,a[i<<1|1].minv);
    }

    void add(int x,int y,int v){
        while(top[x]^top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            add(1,w[top[x]][0],w[x][0],1,sizew,v);
            x=pre[top[x]];
        }
        if(x^y) add(1,min(w[x][0],w[y][0])+1,max(w[x][0],w[y][0]),1,sizew,v);
    }

    int find(){
        if(a[1].minv!=1) return -1;
        return pt[find(1,1,sizew)];
    }
}

namespace Gao2{
    multiset< pair<int,int> > S[MAXN<<2];

    void insert(int x,int y){
        for(int i=(sizew+x-1);i;i>>=1) S[i].insert(make_pair(y,x));
        for(int i=(sizew+y-1);i;i>>=1) S[i].insert(make_pair(x,y));
    }

    void remove(int x,int y){
        for(int i=(sizew+x-1);i;i>>=1) S[i].erase(S[i].find(make_pair(y,x)));
        for(int i=(sizew+y-1);i;i>>=1) S[i].erase(S[i].find(make_pair(x,y)));
    }

    pair<int,int> find(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r){
            multiset< pair<int,int> >::iterator it1=S[x].lower_bound(make_pair(l,0)),it2=S[x].lower_bound(make_pair(r+1,0));
            if(it1!=S[x].begin()) return *(--it1);
            if(it2!=S[x].end()) return *it2;
            return make_pair(-1,0);
        }
        int mid=(cl+cr)>>1;
        if(r<=mid) return find(x<<1,l,r,cl,mid);
        if(l>mid) return find(x<<1|1,l,r,mid+1,cr);
        pair<int,int> temp=find(x<<1,l,r,cl,mid);
        if(temp.first!=-1) return temp;
        else return find(x<<1|1,l,r,mid+1,cr);
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    n=read();
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    dep[1]=1;
    dfs(1,0);
    top[1]=1;
    dfs2(1,0);
    Gao1::init();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        Gao1::add(u,v,1);
        Gao2::insert(w[u][0],w[v][0]);
    }
    for(int i=1;i<n;i++){
        int x=Gao1::find();
        if(x==-1){
            puts("NO");
            return 0;
        }
        pair<int,int> temp=Gao2::find(1,w[x][0],w[x][1],1,sizew);
        assert(temp.first!=-1);
        Gao1::add(pt[temp.first],pt[temp.second],-1);
        Gao1::add(1,w[x][0],w[x][0],1,sizew,2);
        Gao2::remove(temp.first,temp.second);
    }
    puts("YES");
    return 0;
}