【每日一题】7月16日 点权和

点权和

https://ac.nowcoder.com/acm/problem/14393

题意

题意就是给出一棵树,树上所有的节点的权值都是0,现在对一个点进行操作,这个点周围所有的(距离小于等于1 )的点权值都加一,每操作一次,ans加上这个点距离小于等于一的所有点的权值和乘以i(i表示第几次操作),最后输出总的值。

解析

参考了隔壁大佬的博客,大佬博客,大佬的博客实在是难懂,看懂了之后又很明白,首先一步一步来分析

我们要求得是每一次操作之后那个点以及周围所有的权值之和,那么我们可以用一个数组存储操作之后每一个点的贡献,这样每一次操作之后只要查找那个就可以知道权值之和,首先我们看每一次操作对哪些点的贡献会造成影响。
图片说明

在这里就不难看出,每一操作,本身和周围的点权值加一,但是贡献影响到了上下三代,这里的点权和就是4,即这个点的贡献。

那么这里我们要是进行一次操作,会影响到父节点,父节点易得贡献加2,即本身加一,父节点加一,所以父节点的贡献加二,那么爷爷节点呢,因为父节点加一,所以爷爷节点的贡献加一。

每次操作时,我们都要考虑对自己的父亲,父亲的父亲产生的影响,这样做就不必考虑孙子,因为孙子在操作时就会影响到自己,剩下的看代码应该就没有问题了,

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+7;
const int mod=19260817;
ll cnt[N];      //表示这个节点自己被操作了的次数
ll son[N];      //表示这个节点的自己和自己的儿子的贡献之和
ll father[N];   //表示这个父节点对这个节点的贡献
ll fa[N];       //表示储存每一个节点的父节点
ll d[N];        //表示与这个节点相连的所有节点数

int main(void){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i){
        int x;
        scanf("%d",&x);
        fa[i]=x;
        ++d[x],++d[i];
    }
    ll ans=0;
    for(int i=1;i<=m;++i){
        int x;
        scanf("%d",&x);
        ++cnt[x];
        son[x]=(son[x]+d[x])%mod;
        son[fa[x]]=(son[fa[x]]+2)%mod;
        son[fa[fa[x]]]=(son[fa[fa[x]]]+1)%mod;
        father[x]=(father[x]+1)%mod;
        father[fa[x]]=(father[fa[x]]+1)%mod;
        ans=(ans+i*(son[x]+father[fa[x]]+cnt[fa[x]]+cnt[fa[fa[x]]])%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
全部评论

相关推荐

shtdbb_:还不错,没有让你做了笔试再挂你
点赞 评论 收藏
分享
11-03 14:38
重庆大学 Java
AAA求offer教程:我手都抬起来了又揣裤兜了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务