Loading...

洛谷P5018 对称二叉树

check评论:0 条 remove_red_eye浏览量:377 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-08

真是一道简单的普及$T4$...

我们直接暴力就能过这道题...但是讲道理这不是$O(n^2)$的吗...咋就过百万了qwq

我们还是加点优化,最大的点可以快很多

我们记录每个点子树的$size$,$maxdep$,和$sum_{value}$

就可以剪掉很多枝了qwq

其实还可以记录父子结点差值和,会更快

#include <bits/stdc++.h>
using namespace std;
int key[1000010],sum[1000010],dep[1000010],siz[1000010],n,cnt;
int ls[1000010],rs[1000010];
int same(int x,int y)
{
    if(x==y)
    {
        return 1;
    }
    if(x==-1||y==-1)
    {
        return 0;
    }
    if(sum[x]!=sum[y])
    {
        return 0;
    }
    if(dep[x]!=dep[y])
    {
        return 0;
    }
    if(siz[x]!=siz[y])
    {
        return 0;
    }
    return same(ls[x],rs[y])&&same(rs[x],ls[y]);
}
int check(int u)
{
    return same(ls[u],rs[u]);
}
void dfs(int u)
{
    siz[u]=1;
    int maxn=0; 
    if(ls[u]!=-1)
    {
        dep[ls[u]]=dep[u]+1;
        dfs(ls[u]);
        sum[u]+=sum[ls[u]];
        maxn=max(maxn,dep[ls[u]]);
        siz[u]+=siz[ls[u]];
    }
    if(rs[u]!=-1)
    {
        dep[rs[u]]=dep[u]+1;
        dfs(rs[u]);
        sum[u]+=sum[rs[u]];
        maxn=max(maxn,dep[rs[u]]);
        siz[u]+=siz[rs[u]];
    }
    dep[u]=maxn;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&sum[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&ls[i],&rs[i]);
    }
    dfs(1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(check(i))
        {
            ans=max(ans,siz[i]);
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名