FarrisL %%%%%%%%%%%%%%%%%%%%%

mahaorui2012 · 2026-07-17 09:16:21 · 题解

前言

膜拜 @FarrisL 提出随机化做法。这个新做法，复杂度差一点，但仍是一个比较自然的想法。交一个题解记录一下。再次膜拜。%%%%%%%%%%%%%%%%%%%%%%

他的题解。

解法

直接的想法是枚举两个根，这样 BFS 一下就能求出所有叶子了，但是枚举根太慢了。考察叶子所具有性质：

• 度数为 2
• 在一整条度数为 2 的链的正中间。

第二条有特殊情况：整个图是一个环。这意味着树是一个链（若是偶环），否则无解。

但是这不够紧，因为树上可能自带这样的链。

:::success[ 做法 I] 传统做法。

继续发掘性质。考虑链的极端元素，即其首尾。其度数一定不是 2：

• 若度数是 1，则整个图是一个链，若长度为奇数则两端为根，树是一个链，否则无解。
• 否则，最直接的情况是另外一个相邻的链，与当前链的首尾相同，那么这两个链一定都含有叶子。
• 但是可能相邻点全是树上的点，但是若有解，一定是存在两个链符合上一个情况。

这样就找到了至少一对叶子。考虑这有什么用。类似根地，考虑 BFS，其他的点是叶子当且仅当其被松弛了两次。找出这些叶子，断开图，再哈希判树同构即可。O(n+m)。另外，应当在做树哈希的时候加上叶子而不是删去叶子，我因此调了一万年。

另外，这里知道了叶子的对应关系，可以确定性判。但是树哈希太好写了，所以代码里是树哈希。 :::

:::success[做法 II] 大神做法。

但是这已经够了，因为树上这样的无效链的个数很少，小于等于叶子个数，即有效链的个数。

再加上复制出来的链，即至少 \frac{1}{3} 的链为有效链，需要找到至少一个有效链。这显然可以随机化，每次随机取一个链判定即可。做 -\log_{1.5} \epsilon 次判定，可以获得 O((n+m)\log \epsilon) 的复杂度和 \epsilon 的错误率。

判定方法与做法 I 相同。 :::

还有一个什么耳分解做法，但是我不会耳分解，所以咕咕咕。

AC CODE

随机了 44 次。好像刚好能卡着时限通过。

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int N=100005,logeps=44;

vector<int> g[N],h[N];

int fa[2][N],sz[2][N];
void initdsu(int d,int n){
    for(int i=1;i<=n;++i){
        fa[d][i]=i;
        sz[d][i]=1;
    }
}
int find(int d,int x){
    if(fa[d][x]==x) return x;
    return fa[d][x]=find(d,fa[d][x]);
}
void merge(int d,int a,int b){
    a=find(d,a);b=find(d,b);
    if(a==b) return ;
    fa[d][a]=b;
    sz[d][b]+=sz[d][a];
}

int dis[N],cnt[N];
void getbfs(int n,int s){
    for(int i=1;i<=n;++i){
        dis[i]=0;cnt[i]=0;
    }dis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
//      if(s==465) cout<<"bfs ing: -> "<<u<<' '<<dis[u]<<' '<<cnt[u]<<" vvv\n";
        q.pop();
        for(auto x:g[u]){
            if(!dis[x]){
                dis[x]=dis[u]+1;
                cnt[x]=1;
                q.push(x);
//              if(s==465) cout<<"newx: "<<x<<' '<<dis[x]<<' '<<cnt[x]<<'\n';
            }else if(dis[x]==dis[u]+1){
                ++cnt[x];
//              if(s==465) cout<<"oldx: "<<x<<' '<<dis[x]<<' '<<cnt[x]<<'\n';
            }
        }
    }
}

unsigned long long hsh[N];
unsigned long long getnum(unsigned long long x){
    x^=(x>>12);
    x^=(x<<25);
    x^=(x>>27);
    return x;
}
bool checktree(int n,int x){
    int cnt=0;
    for(int i=1;i<=n;++i){
        if(find(1,i)==x){
            cnt+=h[i].size();
        }
    }return cnt/2==sz[1][x]-1;
}
unsigned long long gethash(int u,int fa){
    hsh[u]+=getnum(1);
    for(auto x:h[u]){
        if(x==fa) continue;
        gethash(x,u);
        hsh[u]+=getnum(hsh[x]);
    }return hsh[u];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    initdsu(0,n);
    for(int i=1;i<=n;++i){
        for(auto x:g[i]){
            if(g[i].size()==2 && g[x].size()==2){
                merge(0,i,x);
            }
        }
    }//for(int i=1;i<=n;++i) cout<<"0 dsu: -> "<<i<<" | "<<g[i].size()<<' '
    //                          <<find(0,i)<<' '<<sz[0][find(0,i)]<<'\n';
//  cout<<'\n';

    if(sz[0][find(0,1)]==n){
        if(n&1) cout<<"NO";
        else cout<<"YES";
        return 0;
    }

    vector<int> links;
    for(int i=1;i<=n;++i){
        if(i==fa[0][i] && g[i].size()==2 && (sz[0][i]&1)){
            links.push_back(i);
//          cout<<"inlinks: => "<<i<<'\n';
        }
    }random_shuffle(links.begin(),links.end());
//  cout<<"linksize: "<<links.size()<<'\n';
    for(int lid=0;lid<min(logeps+0ull,links.size()+0ull);++lid){
        int curid=links[lid];
        int linkmid,lst;
        initdsu(1,n);
        for(int i=1;i<=n;++i){
            h[i].clear();
        }for(int i=1;i<=n;++i){
            if(find(0,i)==curid && (g[g[i][0]].size()!=2 || g[g[i][1]].size()!=2)){
                linkmid=i;
                if(g[g[i][0]].size()!=2) lst=g[i][0];
                else lst=g[i][1];
                break;
            }
        }for(int j=1;j<=sz[0][curid]/2;++j){
            int _linkmid=linkmid;
            if(g[linkmid][0]==lst) linkmid=g[linkmid][1];
            else linkmid=g[linkmid][0];
            lst=_linkmid;
        }

//      cout<<"getlink: -> "<<lid<<' '<<curid<<' '<<linkmid<<'\n';
        getbfs(n,linkmid);
//      if(curid==465){
//          for(int i=1;i<=n;++i) cout<<dis[i]<<' ';cout<<'\n';
//          for(int i=1;i<=n;++i) cout<<cnt[i]<<' ';cout<<'\n';
//      }
        bool flag=true;
        for(int i=1;i<=n;++i){
            if(i==linkmid) continue;
            if(!cnt[i] || cnt[i]>2 || (cnt[i]==2 && g[i].size()!=2)){
                flag=false;
                break;
            }if(cnt[i]==1){
                for(auto x:g[i]){
                    if(cnt[x]==1){
                        h[i].push_back(x);
                        merge(1,i,x);
                    }
                }
            }
        }if(!flag) continue;
//      cout<<"get h-graph:\n";
//      for(int i=1;i<=n;++i){
//          cout<<"==> "<<i<<' '<<find(1,i)<<" | ";
//          for(auto x:h[i]){
//              cout<<x<<" ";
//          }cout<<'\n';
//      }

        int fa1=-1,fan=-1;
        for(int i=1;i<=n;++i){
            if(cnt[i]==2 || i==linkmid) continue;
            if(find(1,i)!=fa1){
                if(fa1==-1) fa1=find(1,i);
                else if(fan==-1) fan=find(1,i);
                else if(find(1,i)!=fan){
                    flag=false;
                    break;
                }
            }
        }//cout<<"get fa1/fan: "<<fa1<<' '<<fan<<' '<<flag<<endl;
        if(!flag || fan==-1) continue;  

        if(checktree(n,fa1) && checktree(n,fan)){
//          cout<<"A";
            for(int i=1;i<=n;++i) hsh[i]=0;
            for(int i=1;i<=n;++i){
                if(cnt[i]==2 || cnt[i]==0){
                    hsh[g[i][0]]^=getnum(i);
                    hsh[g[i][1]]^=getnum(i);
                }
            }
            if(gethash(g[linkmid][0],0)==gethash(g[linkmid][1],0)){
                cout<<"YES";
                return 0;
            }
        }
    }cout<<"NO";
    return 0;
}