竞赛讨论区 > 【每日一题】2021年3月29日题目精讲

【每日一题】2021年3月29日题目精讲

头像
王清楚
编辑于 2021-03-29 16:06:25 APP内打开
赞 0 | 收藏 1 | 回复1 | 浏览373

题号 NC200547
名称 划分树
来源 牛客练习赛57
每日一题三期汇总贴~

图片说明
如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿,投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励,可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者:喵渺淼妙的死忠粉
前言
=

题解的解法的赋初值是真没看懂..看了大佬的代码顺便问了大佬数组的含义才懂的这个题..

思路

首先可以知道为根的只有当子树的异或和为才有答案.
其他情况是没有答案的,所以我们可以重构一下树,将树中异或和为的点存起来.
假如,答案显然是.
假如,那么就需要跑树形了.
我们定义表示到了这个节点,的连通块的异或和为的方案数.
很显然的初值是假如这个点标记为,那么.
否则这个点的值就是,那么.
然后通过子树进行转移.
显然:

.

.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1004535809;
const int N=5e5+5;
ll n,M,w[N],id;
ll f[N][2],dp[N][2];
vector<int>g[N];
vector<int>G[N];
bool flag[N];
void dfs1(int u)
{
    for(int v:g[u])
    {
        dfs1(v);
        if(w[v]!=M) w[u]^=w[v];
    }
}

void dfs2(int u,int root)
{
    if(w[u]==0)
    {
        G[root].push_back(++id);
        flag[id]=true;
        root=id;
    }
    else if(w[u]==M)
    {
        G[root].push_back(++id);
        root=id;
    }
    for(int v:g[u])
        dfs2(v,root);
}

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void dfs3(int u)
{
    if(flag[u])    f[u][0]=1;
    else        f[u][1]=1;
    for(int v:G[u])
    {
        dfs3(v);
        dp[u][0]=(f[u][0]*f[v][0]%mod+f[u][1]*f[v][1]%mod+f[u][0]*f[v][1]%mod)%mod;
        dp[u][1]=(f[u][1]*f[v][0]%mod+f[u][1]*f[v][1]%mod+f[u][0]*f[v][1]%mod)%mod;
        f[u][0]=dp[u][0],f[u][1]=dp[u][1];
    }
}

int main()
{
    scanf("%lld%lld",&n,&M);
    for(int i=1;i<n;i++)
    {
        int u;
        scanf("%d",&u);
        g[u].push_back(i+1);
    }
    for(int i=1;i<=n;i++)    scanf("%lld",&w[i]);
    dfs1(1);
    if(w[1]!=M&&w[1]!=0)
    {
        puts("0");
        return 0;
    }
    dfs2(1,0);
    if(M==0)
    {
        printf("%lld\n",qp(2,id-1));
        return 0;
    }
    dfs3(1);
    printf("%lld\n",f[1][1]);
    return 0;
}

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月5日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

1条回帖

回帖
加载中...
话题 回帖

本文相关内容

近期热帖

等你来战

查看全部

热门推荐