首页 > 其他 > 详细

牛客练习赛6 B-点权和

时间:2017-11-18 10:36:48      阅读:394      评论:0      收藏:0      [点我收藏+]
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
#define maxn 100010
#define LL long long
#define mod 19260817
int f[maxn] ;
int sz[maxn];
LL sum[maxn],tag[maxn],sontag[maxn];
int main()
{
#ifdef shuaishuai
    freopen("in.txt","r",stdin );
    //freopen("out.txt","w",stdout);
#endif // shuaishuai
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2,x;i<=n;i++)
    {
        scanf("%d",&x);
        f[i]=x;sz[x]++;sz[i]++;
    }
    LL ans=0;
    for(LL i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        sum[x]+=sz[x]+1;
        sum[f[x]]+=2;
        sum[f[f[x]]]++;
        tag[x]++;
        sontag[f[x]]++;
        LL t=0;//巧妙的容斥- -
        t=(t+sum[x])%mod;//对x操作,x的子节点操作,x的子节点的子节点操作的贡献和
        t=(t+tag[f[x]]*2)%mod;//对fx操作给fx和x带来的累计贡献
        t=(t+tag[f[f[x]]])%mod;//对ffx操作给fx带来的贡献
        t=(t+sontag[f[x]]-tag[x])%mod;//fx子节点中除去x的贡献
        ans=(ans+i*t)%mod;
    }
    printf("%lld\n",ans );
    return 0;
}

 

牛客练习赛6 B-点权和

原文:http://www.cnblogs.com/MeowMeowMeow/p/7854312.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!