CF923F Public Service | Arahc's Home

题面

简化题意

给定两棵树，给第一棵树重标号，使得不存在一对点满足其在两树上都有边直接相连。

$n\leq 10^4$ 。

题解

考虑对于 $n$ 比较小的情况，可以直接暴力做。

显然，对于其中一个树是菊花图的情况，一定是无解的。因为这意味着菊花中心的那个点不能在另一棵树上和任意一个点连边。

否则可以证明一定是有解的。下面我们来考虑构造这样的解。设 $x$ 在另一个图上对应点 $x'$ 。

考虑一个菊花图外挂一个点 $v$ 的情况。显然 $v$ 的度为 $1$ 。我们设与 $v$ 相邻的点为 $u$ ，删掉 $v$ 之后的道德菊花图的中心为 $w$ 。

在另一个图中，找到一个叶子 $w'$ ，将它的父亲标记为 $v'$ ，然后找到任意一个不与 $v'$ 相邻的点，将其标为 $u'$ 。剩下的点就可以随便乱搞了。

然后考虑更为一般的情况。采用归纳构造：在第一棵树里面找到两个叶子 $u,v$ 满足 $dis(u,v)\geq 3$ 且原图去掉这两个点之后不会变成菊花图。

注意到要么 $n$ 比较小，要么原图是菊花图外挂一个点，否则这样的点一定是存在的。在另一个树上也找到这样的一对点 $u',v'$ ，然后将这四个点删掉即可。直到其中至少一个图出现了 $n$ 较小时或者原图变成了菊花外挂一个点时，用特殊方法解决。至于删去的点，我们在回溯的时候判定一下选择 $u\to u',v\to v'$ 这样的对应还是 $u\to v',v\to u'$ 这样的对应即可。

考虑每次找点删点是 $\mathcal O(n^2)$ 的，如何快速优化这一过程。

考虑我们可以通过这样的方法找一对 $u,v$ ：任意选择一个叶子 $u$ ，找出与这个叶子相邻的点 $x$ ，然后任意选择一个不与 $x$ 相邻的点 $v$ 。

对于每个点开一个 set 维护与它相邻的叶子，再开一个 set 维护相邻点里有叶子的结点。每次随便找一个结点的一个叶子，再随便找另一个结点的一个叶子即可。

复杂度为 $\mathcal O(n\log n)$ ，可以很轻松地通过此题。

代码

#include<bits/stdc++.h>
// #define int long long
using namespace std;
bool Begin;
const int max_n=300005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n;

set< pair<int,int> > sA,sB;
set<int> leaf[max_n<<1],g[max_n<<1];

int ans[max_n];

inline void ValueOne(set< pair<int,int> > &s1,set< pair<int,int> > &s2,int n){
    bool rev=0;
    if(s1.rbegin()->first!=n-3){
        swap(s1,s2);
        rev=1;
    }
    int w=s1.rbegin()->second,u=next(s1.rbegin())->second,v=*leaf[u].begin();
    ans[v]=s2.rbegin()->second;
    ans[w]=*leaf[ans[v]].begin();
    for(auto p:s2) if(g[ans[v]].find(p.second)==g[ans[v]].end()){
        ans[u]=p.second;
        break;
    }
    auto it=s2.begin();
    for(auto p:s1) if(!ans[p.second]){
        while(it->second==ans[u] || it->second==ans[v] || it->second==ans[w])
            ++it;
        ans[p.second]=it->second;
        ++it;
    }
    if(rev) for(auto p:s1)
        ans[ans[p.second]]=p.second;
}
inline void SmallGraph(set< pair<int,int> > &s1,set< pair<int,int> > &s2,int n){
    map<int,int> mp;
    vector<int> vec,A,B;
    for(auto p:s1) A.emplace_back(p.second);
    for(auto p:s2) B.emplace_back(p.second);
    for(int i=0;i<n;++i) vec.emplace_back(i);
    do{
        mp.clear();
        for(int i=0;i<n;++i)
            mp[A[vec[i]]]=B[i];
        bool ok=1;
        for(int i=0;i<n && ok;++i)
            for(auto p:g[A[vec[i]]])
                if(g[B[i]].find(mp[p])!=g[B[i]].end()){
                    ok=0;
                    break;
                }
        if(ok){
            for(int i=0;i<n;++i)
                ans[A[vec[i]]]=B[i];
            return;
        }
    }while(next_permutation(vec.begin(),vec.end()));
}

inline void Delete(set< pair<int,int> > &s,int x){
    int y=*g[x].begin();
    s.erase(make_pair(0,x));
    s.erase(make_pair(leaf[y].size(),y));
    leaf[y].erase(x);
    s.emplace(leaf[y].size(),y);
    g[y].erase(x);
    if(g[y].size()==1){
        int z=*g[y].begin();
        s.erase(make_pair(leaf[z].size(),z));
        leaf[z].emplace(y);
        s.emplace(leaf[z].size(),z);
    }
}

inline void solve(set< pair<int,int> > &s1,set< pair<int,int> > &s2){
    int n=s1.size();
    if(s1.rbegin()->first==n-3 || s2.rbegin()->first==n-3) return ValueOne(s1,s2,n);
    if(n<7) return SmallGraph(s1,s2,n);
    int a=s1.rbegin()->second,b=next(s1.rbegin())->second,c=s2.rbegin()->second,d=next(s2.rbegin())->second;
    int u1=*leaf[a].begin(),v1=*leaf[b].begin(),u2=*leaf[c].begin(),v2=*leaf[d].begin();
    Delete(s1,u1),Delete(s1,v1),Delete(s2,u2),Delete(s2,v2);
    solve(s1,s2);
    if(g[u2].find(ans[a])==g[u2].end() && g[v2].find(ans[b])==g[v2].end())
        ans[u1]=u2,ans[v1]=v2;
    else
        ans[u1]=v2,ans[v1]=u2;
}

bool End;
#define File "vvakioi"
signed main(){
    #ifndef ONLINE_JUDGE
    freopen(File ".in","r",stdin);
    freopen(File ".out","w",stdout);
    #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    n=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].emplace(v),g[v].emplace(u);
    }
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].emplace(v),g[v].emplace(u);
    }
    for(int i=1;i<=(n<<1);++i){
        if(g[i].size()==n-1) return puts("No"),0;
        if(g[i].size()==1) leaf[*g[i].begin()].emplace(i);
    }
    for(int i=1;i<=n;++i)
        sA.emplace(leaf[i].size(),i);
    for(int i=n+1;i<=(n<<1);++i)
        sB.emplace(leaf[i].size(),i);
    solve(sA,sB);
    puts("Yes");
    for(int i=1;i<=n;++i)
        write(ans[i]),putchar(' ');
    return 0;
}