题解 P4323 【[JSOI2016]独特的树叶】

· · 题解

前言

这题调了我两天，最终在机房大佬的指导下A了。 泪目，发题解庆祝一下。

题意

给出两棵树 A，B，要求判断出 B 去掉哪个叶子与 A 同构（不知道树的同构的同学可以去这里）。

思路

考虑树哈希（蒻蒟不会直径之类的判同构qwq）。

这里采用 hash(u)=size(u)\times\sum_{i}hash(v)*base^{i - 1}\mod P 的方式做哈希。

注意一点注意一点！P 和 base 的选择不能选小了（不然就会少分，嗯，别问我咋知道的。

哈希的一个重要性质就是对于 \sqrt P 以下的数据冲突概率极小，但无法保证\sqrt P以上的，所以P和base选择要合适。

然后就是转移问题，考虑二次扫描换根树形dp。

插入时处理一个 degree(u) 表示 B 中每个节点的度。

然后先以 1 为根扫一遍 dfs，记录下每个节点的父节点 f_{u} ，哈希值hash(u)，子树大小size(u)，以及子树的哈希值集合 t(u) 。

对于每一个节点 u，设g(u)表示u为根时子树f_{u}的哈希值（这里f_{u}指的是刚刚预处理出的数据，然后每个点的哈希值就是g(u)和t(u)合并而来。

那么怎么维护g(u)？

注意到t(u)与g(u)（如果g(u)存在）共同构成的集合中，去掉hash(v)就是g(v)，所以我们维护一个前缀一个后缀，二分查找到hash(v)的位置后前后缀一拼就是g(v)。

emm如果没看懂，就，结合代码，再画画图，应该，就行，了。

查询就简单了，A中的所有点作为根对应的哈希值用个set什么的记录一下，然后在做B的哈希的时候查找，如果有度数为1的点与A的哈希有重合就用它更新答案

注意1要特殊处理，因为dfs无法查到1。

（PS 这种前后缀合并的思想在换根dp中蛮常用，记到就是赚到）

关于代码

因为调了蛮久，所以可能有点丑陋。而且其实可以对于A,B，dfs1和dfs2完全可以合并，只需要记录一个是否是B的变量来判断执行记录操作还是查找操作就行了，也可以只建一个图（然后我这个憨批没想到5555）。

最后注意哈希值的选择

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using std::vector;
using std::sort;
using std::lower_bound;
using std::set;
typedef long long ll;
const int N = 1e5 + 10, base = 1000000021, mod = 999999137;
struct edge
{
    int v, next;
}A[N * 2], B[N * 2];
int a[N], b[N], ca, cb, n, ans = 99999999, faa[N], fab[N], deg[N];

void init()
{
    memset(a, -1, sizeof a);
    memset(b, -1, sizeof b);
    ca = cb = 0;
}

void insertA(int u, int v)
{
    A[ca].v = v;
    A[ca].next = a[u];
    a[u] = ca++;
}

void insertB(int u, int v)
{
    B[cb].v = v;
    deg[u]++;
    B[cb].next = b[u];
    b[u] = cb++;
}

ll hashA[N], hashB[N], sza[N], szb[N];
vector<ll> ta[N], sla[N], sra[N], tb[N], slb[N], srb[N];
ll dfsA1(int u, int fa)
{
    ta[u].clear(), faa[u] = fa, sza[u] = 1;
    ll ret = 0;
    for (int i = a[u]; i + 1; i = A[i].next)
    {
        int v = A[i].v;
        if (v == fa)
            continue;
        ta[u].push_back(dfsA1(v, u));
        sza[u] += sza[v];
    }
    if (ta[u].empty())
        return hashA[u] = 1;

    sort(ta[u].begin(), ta[u].end());
    for (int i = 0; i < (int)ta[u].size(); i++)
        ret = (ret * base + ta[u][i]) % mod;
    return hashA[u] = (ret * sza[u]) % mod;
}

ll dfsB1(int u, int fa)
{
    tb[u].clear(), fab[u] = fa, szb[u] = 1;
    ll ret = 0;
    for (int i = b[u]; i + 1; i = B[i].next)
    {
        int v = B[i].v;
        if (v == fa)
            continue;
        tb[u].push_back(dfsB1(v, u));
        szb[u] += szb[v];
    }
    if (tb[u].empty())
        return hashB[u] = 1;

    sort(tb[u].begin(), tb[u].end()); 
    for (int i = 0; i < (int)tb[u].size(); i++)
        ret = (ret * base + tb[u][i]) % mod; 
    return hashB[u] = (ret * szb[u]) % mod;
}

ll gA[N], gB[N], pb[N];
set<ll> vis;
void dfsA2(int u)
{
    if (faa[u] != -1)
    {
        ta[u].push_back(gA[u]);
        sort(ta[u].begin(), ta[u].end());
    }
    int sze = ta[u].size();
    sla[u].resize(sze);
    sla[u][0] = ta[u][0];
    for (int i = 1; i < sze; i++)
        sla[u][i] = (sla[u][i - 1] * base + ta[u][i]) % mod;

    sra[u].resize(sze);
    sra[u][sze - 1] = ta[u][sze - 1];
    for (int i = sze - 2; i >= 0; i--)
        sra[u][i] = (sra[u][i + 1] + ta[u][i] * pb[sze - i - 1]) % mod;

    for (int i = a[u]; i + 1; i = A[i].next)
    {
        int v = A[i].v;
        if (v == faa[u])
            continue;           
        if (sze == 1)
        {
            gA[v] = 1;
            dfsA2(v);
            break;
        }
        int p = lower_bound(ta[u].begin(), ta[u].end(), hashA[v]) - ta[u].begin();
        gA[v] = 0;
        if (p + 1 < sze)
            gA[v] = sra[u][p + 1];
        if (p - 1 >= 0)
            gA[v] = (gA[v] + sla[u][p - 1] 
            * pb[sze - 1 - p]) % mod;
        gA[v] = gA[v] * (n - sza[v]) % mod;
        dfsA2(v);

    } 
    vis.insert(sla[u][sze - 1] * n % mod);  
}

void dfsB2(int u)
{
    if (fab[u] != -1)
    {
        tb[u].push_back(gB[u]);
        sort(tb[u].begin(), tb[u].end());
    }
    int sze = tb[u].size();
    slb[u].resize(sze);
    slb[u][0] = tb[u][0];
    for (int i = 1; i < sze; i++)
        slb[u][i] = (slb[u][i - 1] * base + tb[u][i]) % mod;

    srb[u].resize(sze);
    srb[u][sze - 1] = tb[u][sze - 1];
    for (int i = sze - 2; i >= 0; i--)
        srb[u][i] = (srb[u][i + 1] + tb[u][i] * pb[sze - i - 1]) % mod;

    for (int i = b[u]; i + 1; i = B[i].next)
    {
        int v = B[i].v;
        if (v == fab[u])
            continue;       
        if (sze == 1)
        {
            gB[v] = 1;
            dfsB2(v);
            break;
        }
        int p = lower_bound(tb[u].begin(), tb[u].end(), hashB[v]) - tb[u].begin();
        gB[v] = 0;
        if (p + 1 < sze)
            gB[v] = srb[u][p + 1];
        if (p - 1 >= 0)
            gB[v] = (gB[v] + slb[u][p - 1] * pb[sze - 1 - p]) % mod;
        gB[v] = gB[v] * (n - szb[v]) % mod;
        if (deg[v] == 1 && vis.find(gB[v]) != vis.end())
            ans = std::min(ans, v); 
        dfsB2(v);   
    } 
}

int main()
{
    init();
    pb[0] = 1;
    for (int i = 1; i < N; i++)
        pb[i] = pb[i - 1] * base % mod;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        insertA(x, y);
        insertA(y, x);
    }
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        insertB(x, y);
        insertB(y, x);
    }
    dfsA1(1, -1);
    dfsA2(1);
    n++;
    dfsB1(1, -1);
    if(deg[1] == 1 && vis.find(hashB[B[b[1]].v]) != vis.end())
        ans = 1;
    dfsB2(1);
    printf("%d", ans);
    return 0;
}