2019icpc西安邀请赛 J And And And （树形dp）

你的名字 2021-10-30 02:38 388阅读 0赞

题目链接：https://nanti.jisuanke.com/t/39277

题意：给出一棵有边权的树，求所有简单路径包含异或和为0的简单路径的总数和。

思路：

首先，对于异或为0这一限制，我们通过dfs得到根节点到所有点的路径上的异或和val\[i\]，如果两个结点的val值相等，说明他们之间的路径满足异或和为0。sz \[i\]为以i为根的子树　的大小。

其次，对于满足异或和为0的两个点u、v，分两种情况考虑：

1. u、v在不同链上，这一条路径的贡献值为sz\[u\]\*sz\[v\]，通过map记录每一种权值的size和即可得到。我们先将所有点这样处理一遍。

2. u、v在一条链上，这一条路径的贡献值为(n-sz\[u1\])\*sz\[v\]，u1是u与v这一条链上u的第一个子结点。因为上一步我们把所有情况加上了，所以要先减去sz\[u\]\*sz\[v\]，通过mp1来记录同一条链上异或值为val的size和，因为是记录同一条链，所以当处理完一个结点的所有子结点时要回溯更新，即减去前面加的size。减了之后加上(n-sz\[u1\])\*sz\[v\]，通过mp2来记录该信息，每处理完一个子结点时回溯更新，因为已经不在一条链上。

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<unordered_map>
    using namespace std;
    
    const int maxn=1e5+5;
    const int MOD=1e9+7;
    typedef long long LL;
    typedef unordered_map<LL,LL> ump;
    struct node{
        int v,nex;
        LL w;
    }edge[maxn];
    
    int n,head[maxn],cnt,sz[maxn];
    LL val[maxn],ans;
    ump sum,mp1,mp2;
    
    void adde(int u,int v,LL w){
        edge[++cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].nex=head[u];
        head[u]=cnt;
    }
    
    void dfs1(int u,LL va){
        val[u]=va,sz[u]=1;
        for(int i=head[u];i;i=edge[i].nex){
            int v=edge[i].v;
            LL w=edge[i].w;
            dfs1(v,va^w);
            sz[u]+=sz[v];
        }
    }
    
    void dfs2(int u){
        ans=(ans+sum[val[u]]*sz[u])%MOD;
        sum[val[u]]=(sum[val[u]]+sz[u])%MOD;
        for(int i=head[u];i;i=edge[i].nex)
            dfs2(edge[i].v);
    }
    
    void dfs3(int u){
        ans=(ans-mp1[val[u]]*sz[u]+mp2[val[u]]*sz[u]+MOD)%MOD;
        mp1[val[u]]=(mp1[val[u]]+sz[u])%MOD;
        for(int i=head[u];i;i=edge[i].nex){
            int v=edge[i].v;
            LL w=edge[i].w;
            mp2[val[u]]=(mp2[val[u]]+n-sz[v]+MOD)%MOD;
            dfs3(v);
            mp2[val[u]]=(mp2[val[u]]-n+sz[v]+MOD)%MOD;
        }
        mp1[val[u]]=(mp1[val[u]]-sz[u]+MOD)%MOD;
    }
    
    int main(){
        scanf("%d",&n);
        for(int i=2;i<=n;++i){
            int u;LL w;
            scanf("%d%lld",&u,&w);
            adde(u,i,w);
        }
        dfs1(1,0);
        dfs2(1);
        dfs3(1);
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/11371882.html