【每日一题】 点权和
点权和
https://ac.nowcoder.com/acm/problem/14393
点权和
解题思路：我们统计每个结点的时候，需要考虑自己本身的贡献、自己父亲的贡献以及自己儿子的贡献
1.自己的贡献：由自己操作的次数和父亲操作的次数和儿子操作的次数构成
2.父亲的贡献：由自己操作的次数和父亲操作的次数和父亲的父亲操作的次数
3.儿子的贡献：由自己的操作次数*孩子的个数和他儿子+1的次数和他孙子+1的次数构成
接下来就是如何进行上述的求解
我们可以用三个数组分别表示自己的操作次数、自己的儿子操作的次数、自己的孙子操作的次数(a[x],b[x],c[x])
每次操作都要使a[x]++,同时再使得b[fa[x]]++,同时使得c[fa[fa[x]]]++
#include<bits/stdc++.h>
using namespace std;
const int mode=19260817;
const int maxn=1e5+10;
long long sonsize[maxn],a[maxn],b[maxn],c[maxn],fa[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
fa[i]=x;
sonsize[x]++;
}
long long ans=0;
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x]++;
if(fa[x]!=0) b[fa[x]]++;
if(fa[fa[x]]!=0) c[fa[fa[x]]]++;
long long f1=(a[fa[x]]+b[fa[x]]+a[fa[fa[x]]])%mode;
long long f2=(a[x]+a[fa[x]]+b[x])%mode;
long long f3=(sonsize[x]*a[x]%mode+b[x]+c[x])%mode;
long long res=(f1+f2+f3)%mode;
ans=(ans+i*res%mode)%mode;
}
printf("%lld\n",ans);
return 0;
} 
腾讯公司福利 448人发布
