题号 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. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴