点权和 | 思维统计

题解：

我试图去遍历邻接表（以为是水题），结果T飞了呀——m1e7，随便出点数据就可以卡了。

看一下正解：

用一个数组表示，当前这个点操作了几次，那么就如上图所示，绿色的点操作x次对此次操作的贡献即为2x，蓝色的点为1x。

很显然x的操作次数的贡献为：x的度数+1。

所以显然需要维护邻接点，但是这个邻接点不太好维护，考虑树的性质:一个点的父亲节点有且只有一个。

那么就想到维护 父亲节点。

首先解释一下下面所用到的所有数组：

tag[x] ，x节点被操作了几次

ftag[x]，x节点作为被操作节点的父节点的次数

gftag[x]，x节点作为被操做节点爷爷节点的次数

设tag[i]表示第i个节点操作了多少次,那么我们把问题分解开，也就是一个节点向下的贡献(儿子及孙子)与向上的贡献之和(父亲及爷爷)最后再加上这个点的贡献。

1.考虑向下的贡献：

怎么知道x有几个儿子节点呢被操作了呢，因为树的父亲节点只有一个，所以可以在对儿子进行操作时，用一个数组ftag[i]辅助，ftag[i]表示i作为父节点一共被操作了多少次，反过来也就是说ftag[i]表示i节点的所有儿子的贡献。

例如对x点进行操作那么:ftag[fa[x]]++

同理，当对孙子进行操作时考虑爷爷的贡献。fftag[i]表示i的所有孙子节点的的贡献

所以向下的贡献也就非常容易算了：

2.考虑向上的贡献：

因为父亲只有一个：那么答案首先要加上tag[fa[x]]，表示父亲被操作了多少次。

接下来就是爷爷的贡献：tag[fa[fa[x]]]

但是这时候注意，向上的贡献没有考虑完全：可能一个点y是x的兄弟节点，如果y被操作了的话，x的父亲节点也会被更新，也就是说父亲节点作为父亲节点的时候也有1的贡献。所以答案还需要加上ftag[fa[x]]但是此时父亲节点作为父亲节点时候的贡献包含作为x节点父亲的贡献，而不完全是兄弟节点的。所以ftag[fa[x]]-tag[x]是父亲作为兄弟节点的贡献。

所以向上的贡献为：

3.最后考虑自己对所有邻接点的贡献 :

所以每次操作后的结果就是 上述所有贡献之和，可以发现答案完全可以用Om的复杂度去维护

Code：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const ll INF=1e18;
const int maxn=5e5+18;
const int mod=19260817;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll tag[maxn];
ll ftag[maxn];
ll gftag[maxn];
int fa[maxn];
ll in[maxn];
int main()
{
    read(n);read(m);
    for(int i=2;i<=n;i++){
        int x;scanf("%d",&x);
        fa[i]=x;
        in[i]++;in[x]++;
    }
    ll ans=0;
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);
        ll temp=0;
        tag[x]=(tag[x]+1)%mod;///当前节点影响加1
        if(fa[x]){///存在父亲节点 该父亲节点被儿子节点影响了一次
            ftag[fa[x]]=(ftag[fa[x]]+1)%mod;///fa[x]作为父节点的次数++
            temp=(temp+tag[fa[x]]*2+(ftag[fa[x]]-tag[x]))%mod;///父亲节点被操作的次数 对答案的贡献为*2
        }
        if(fa[fa[x]]){///存在爷爷节点
            gftag[fa[fa[x]]]=(gftag[fa[fa[x]]]+1)%mod;
            temp=(temp+tag[fa[fa[x]]])%mod;///爷爷节点对该点的影响为1
        }
        temp=(temp+(in[x]+1)*tag[x]+ftag[x]*2+gftag[x])%mod;
        ans=(ans+i*temp%mod)%mod;
    }
    printf("%lld\n",(ans)%mod);
    return 0;
}