P4323

orpg · 2023-07-17 14:37:59 · 题解

题目传送门

题目梗概

在 B 树上寻找一个叶子节点，使得 B 树在删除这个叶子后与 A 树一样。

题意分析

题目要求我们对比两颗树是否一样，暴力算法 O(n^2) 过不了。所以我们想到了树上哈希。

对于一个节点 u 我们维护一个数组 f_u 表示以 u 为根的子树的哈希值。因为编号打乱，所以如果只以 u 为根，那么有可能找不到。我们再通过换根 dp 维护一个 g_u 数组，就可以找到叶子节点了。

为了方便找到，我们先维护以变 A 树的 f_u 和 g_u 然后将 g_u 丢进一个 set 中(可以在 O(n \log n) 的时间找到) 最后将 B 树的哈希 g_u 减掉一个叶子节点。判断是否和 A 树一样。

上代码

#include<bits/stdc++.h>
#define ull unsigned long long
#define int ull
using namespace std;
const int maxn=2e6+5;
struct node{
    int to,nxt;
}ed[maxn];
int head[maxn<<1];
int n,tot,siz[maxn];
ull f[maxn],g[maxn];
int prime[maxn];
int io[maxn];
int fa[maxn];
bool isprime[maxn];
set<int> st;
void add(int u,int v){
    ed[++tot].to=v;
    ed[tot].nxt=head[u];
    head[u]=tot;
}
void er(int n){
    memset(isprime,true,sizeof(isprime));
    prime[0]=0;
    for(int i=2;i<=n;i++){
        if (isprime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0] && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=false;
            if (i%prime[j]==0) break;
        }
    }
}
void dfs(int u,int fa){
    siz[u]=1;
    f[u]=1;
    for(int i=head[u];i;i=ed[i].nxt){
        int to=ed[i].to;
        if(to==fa) continue;
        dfs(to,u);
        siz[u]+=siz[to];
        f[u]+=f[to]*prime[siz[to]];
    }
}
void dfs1(int u,int fa,int tmp){
    g[u]=f[u]+tmp*prime[n-siz[u]];
    for(int i=head[u];i;i=ed[i].nxt){
        int to=ed[i].to;
        if(to==fa) continue;
        int temp=g[u]-f[to]*prime[siz[to]];
        dfs1(to,u,temp);
    }
}
void init(){
    tot=0;
    memset(head,0,sizeof head);
    memset(g,0,sizeof(g));
    memset(f,0,sizeof f);
    memset(siz,0,sizeof siz);
}
main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    er(1299710);
    for(int a,b,i=1;i<n;i++){
        cin>>a>>b;
        add(a,b);add(b,a);
    }
    dfs(1,0);
    dfs1(1,0,0);
    for(int i=1;i<n;i++){
        st.insert(g[i]);
    }
    init();
    n++;//本人代码在此挂了3次
    //因为dfs 和 dfs1会用到n,所以n必须更新为当前节点数
    for(int a,b,i=1;i<n;i++){
        cin>>a>>b;
        add(a,b);add(b,a);
        io[a]++,io[b]++;
    }
    dfs(1,0);
    dfs1(1,0,0);
    for(int i=1;i<=n;i++){
        if(io[i]!=1) continue;
        int fo=(g[ed[head[i]].to]-2);
        if(st.find(fo)!=st.end()){
            cout<<i<<'\n';
            return 0;
        }
    }
    return 0;
}