【每日一题】 点权和

点权和

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;
}