点权和

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

感谢sunsetcolors大佬的博客，提供思路

首先题意需要仔细看，大致就是，给你一棵树，开始每个点权都是0，m次操作，每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k， ans=k*i。 i表示每次操作的编号

分析: 由于m=1000000很大。建树暴力加是妥妥TLE了。本人亲测只能对30。

那么这题的突破口就是树上距离小于等于1的点，可以从每个点影响周围点的贡献入手。一个点无非就是影响他的儿子，他的父亲，他自己。

所以只要把这个点父亲节点的贡献+这个点儿子节点的贡献+这个点本身的贡献就完事了

定义数组 now[x] 表示节点x被操作的次数
son[x] 表示节点x的儿子被操作的次数
b[x] 表示节点x的孙子被操作的次数为什么要孙子，因为在处理儿子节点的贡献时，孙子节点对儿子节点会产生影响的。

具体细节在代码注释里

AC代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define PI 3.14159265358979323846

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const ll MOD=19260817;

const int N=100000+100;

int n,m,x; 
ll now[N];//表示当前节点被操作的次数
ll son[N];//表示儿子节点被操作的次数
ll b[N];  //表示孙子节点被操作的次数 
ll fa[N]; //表示当前节点的父亲节点是谁 

int siz[N];//表示当前节点儿子的数量 

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d",&x);
        fa[i+1]=x; 
        siz[x]++; 
    }
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        ll k=0;

        now[x]++;//当前节点x被操作了一次
        if(fa[x]!=0)son[fa[x]]++;//如果当前节点的父亲存在，那么这个父亲节点的儿子操作次数++ 
        if(fa[fa[x]]!=0)b[fa[fa[x]]]++;//如果当前节点父亲的父亲存在，说明当前节点是fa[fa[x]]的孙子节点，那么孙子节点也要++ 


        //处理父亲节点的贡献
        k=k+now[fa[x]]%MOD+son[fa[x]]%MOD+now[fa[fa[x]]]%MOD; //父亲节点自己被操作的次数now[fa[x]]
                                                 // 父亲节点儿子被操作的次数son[fa[x]]
                                                 //父亲节点的父亲节点自己被操作的次数now[fa[fa[x]]] 
        k%=MOD;
        //处理自己节点的贡献

        k=k+now[x]%MOD+son[x]%MOD+now[fa[x]]%MOD;   //自己节点本身被操作的次数now[x]
                                        //自己节点儿子被操作的次数son[x]
                                        //自己节点的父亲被操作的次数now[fa[x]] 
        k%=MOD;
        //处理儿子节点的贡献 

        k=k+(siz[x]*now[x])%MOD+son[x]%MOD+b[x]%MOD; //当前节点操作一次，儿子节点对应也要操作， 儿子节点总贡献 siz[x]*now[x] 

        k%=MOD;

        ans+=(k*i)%MOD;

        ans%=MOD;
    }
    printf("%lld\n",ans%MOD);
    return 0;
}