NOIP2018普及T4题解

· · 题解

假设题中要求的不是对称而是左子树和右子树完全相同

我们知道，一棵子树的dfs序在整颗树的dfs序中是连续的一段区间

那我们就可以按照dfs前序遍历预处理出dfs序（以权值为元素），确定以每个点为根的子树在总dfs序中的位置，那就把问题转换成了两个序列是否相同的问题：每个点的左子树和右子树分别看成一个序列，判断是否相等

但是稍微一想就会发现这个算法存在问题

即便Dfs序相同，这两个子树有可能仅仅只是前序遍历相同，但结构并不相同

怎么办呢？

我们考虑把所有缺少左或右儿子（包括叶子节点）的节点都添上权值为-1的点作为它们的儿子

样例2被改造如下：

改造完以后再做前序遍历，这样就可以保证对于相同的dfs序的两棵子树不只是权值相同，而且结构相同

（这个结论是我自己YY出来的，自己也不会证，如果有Hack数据可以在洛谷里私信我）

判断两个序列是否相等，哈希实现

至于对称，我们只要先做一遍“左子树->根->右子树”的前序遍历，再做一遍“右子树->根->左子树”，处理出两个序列，判断左子树的第一个序列和右子数的第二个序列是否相同即可

代码如下：

# include <cstdio>
# define N 1000010
int v[N],l[N],r[N],dfn[N<<1],a[N],b[N],m,siz[N];
unsigned long long sum[N<<1],p1003[N<<1],z[N],f[N];//用unsigned long long自动取模
int dmax(int x,int y) {return x>y?x:y;}
void dfs1(int x) {//左根右
    int i;
    if(x==-1) {
        dfn[++m]=0;
        return;
    }
    siz[x]=1;//子树大小
    dfn[++m]=v[x]+1;//因为有-1不好处理，因此全部+1
    a[l[x]]=m+1;//dfs序起点
    dfs1(l[x]);
    b[l[x]]=m;//dfs序终点
    if(l[x]) siz[x]+=siz[l[x]];
    a[r[x]]=m+1;
    dfs1(r[x]);
    b[r[x]]=m;
    if(r[x]) siz[x]+=siz[r[x]];
    return;
}
void dfs2(int x) {//右根左
    int i;
    if(x==-1) {
        dfn[++m]=0;
        return;
    }
    dfn[++m]=v[x]+1;
    a[r[x]]=m+1;
    dfs2(r[x]);
    b[r[x]]=m;
    a[l[x]]=m+1;
    dfs2(l[x]);
    b[l[x]]=m;
    return;
}
int main() {
    int n,i,ans=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++) {
        scanf("%d",v+i);
    }
    for(i=1;i<=n;i++) {
        scanf("%d%d",l+i,r+i);
    }
    m=0;
    dfs1(1);
    a[1]=1;b[1]=m;
    p1003[0]=1;
    for(i=1;i<=m;i++) {
        p1003[i]=p1003[i-1]*1003;
        sum[i]=sum[i-1]*1003+dfn[i];
    }
    for(i=1;i<=n;i++) {
        z[i]=sum[b[i]]-sum[a[i]-1]*p1003[b[i]-a[i]+1];
    }
    m=0;
    dfs2(1);
    a[1]=1;b[1]=m;
    for(i=1;i<=m;i++) {
        sum[i]=sum[i-1]*1003+dfn[i];
    }
    for(i=1;i<=n;i++) {
        f[i]=sum[b[i]]-sum[a[i]-1]*p1003[b[i]-a[i]+1];
    }
    for(i=1;i<=n;i++) {//比对，找最大的答案
        if(z[l[i]]==f[r[i]]) {
            ans=dmax(ans,siz[i]);
        }
    }
    printf("%d",ans);
    return 0;
}