【每日一题】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; }