M_sea

洛谷4323 [JSOI2016]独特的树叶
LuoguBZOJ分析树 $\mathrm{hash}$ + 换根 $\mathrm{DP}$ 。先考虑一个 $O...
扫描右侧二维码阅读全文
07
2019/05

洛谷4323 [JSOI2016]独特的树叶

Luogu

BZOJ

分析

树 $\mathrm{hash}$ + 换根 $\mathrm{DP}$ 。

先考虑一个 $O(n^2)$ 的做法。

先求出以每个节点为根,整棵树的 $\mathrm{hash}$ 值。可以做 $n$ 遍 $\mathrm{dfs}$ 得到。

然后,把 $A$ 的所有 $n$ 个 $\mathrm{hash}$ 值丢到一个 $\mathrm{map}$ 里去,然后枚举 $B$ 的每一个叶子节点,判断删掉后的哈希值是否在 $\mathrm{map}$ 中即可。

这个算法的主要瓶颈在于 $O(n^2)$ 求 $\mathrm{hash}$ 值,我们考虑优化这个过程。

异或满足可减性,很容易抵消掉。所以我们设哈希函数 $f_i=\bigoplus\limits_{j\in Son_i}(f_j\times W+sz_j)$ 。

对于每棵树,我们设 $f_i$ 表示上面的哈希函数, $h_i$ 为以 $i$ 为根时整棵树的 $\mathrm{hash}$ 值。

这样就可以先一遍 $\mathrm{dfs}$ 求出 $f$ ,再一遍换根 $\mathrm{DP}$ 求出 $h$ 了。

具体的,$h_i=f_i\oplus\Big\{\big[h_{fa}\oplus(f_i\times W+sz_i)\big]\times W+(n-sz_i)\Big\}$ 。特殊的是当 $i$ 为根时 $h_i=f_i$ 。

这个式子不太好解释,建议自己画图理解。

那么这样子求 $\mathrm{hash}$ 值就降到了 $O(n)$ ,总时间复杂度为 $O(n\log n)$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200001+10;
const int BASE=19491001;

struct Tree {
    int n;
    
    struct Edge { int v,nxt; } e[N<<1];
    int head[N];

    inline void addEdge(int u,int v) {
        static int cnt=0;
        e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
    }
    
    unsigned int f[N],h[N];
    int sz[N];

    inline void dfs1(int u,int fa) {
        sz[u]=1;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (v==fa) continue;
            dfs1(v,u),f[u]^=(f[v]*BASE+sz[v]),sz[u]+=sz[v];
        }
    }
    inline void dfs2(int u,int fa) {
        if (!fa) h[u]=f[u];
        else h[u]=f[u]^((h[fa]^(f[u]*BASE+sz[u]))*BASE+(n-sz[u]));
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=fa) dfs2(e[i].v,u);
    }
} A,B;

int deg[N];
map<unsigned int,bool> M;

int main() {
    int n=read(); A.n=n,B.n=n+1;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        A.addEdge(u,v),A.addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) {
        int u=read(),v=read();
        B.addEdge(u,v),B.addEdge(v,u);
        ++deg[u],++deg[v];
    }
    A.dfs1(1,0),A.dfs2(1,0);
    for (re int i=1;i<=n;++i) M[A.h[i]]=1;
    for (re int i=1;i<=n+1;++i)
        if (deg[i]>1) { B.dfs1(i,0),B.dfs2(i,0); break; }
    for (re int i=1;i<=n+1;++i) {
        if (deg[i]>1) continue;
        int v=B.e[B.head[i]].v,w=B.h[v]^(B.f[i]*BASE+1);
        if (M[w]) { printf("%d\n",i); break; }
    }
    return 0;
}
最后修改:2019 年 05 月 07 日 08 : 04 PM

发表评论