点权和 题解

点权和题解

题目分析：

一道以空间换时间的题目。关键在维护什么和怎么维护才能高效地得到答案。
通过仔细又认真地观察，再加上一点灵感，可以发现。每个点位置处地答案可以由这个点和与它距离小于等于2点的更新次数马上得到。
设有一个点，记为v，如果我们知道下面几个量，那么此时v处的答案可以在O(1)的时间马上得到：

1. 当前结点父亲的父亲的更新次数cntff
2. 当前结点的父亲的更新次数cntf
3. 当前结点的更新次数cnt
4. 当前结点所有儿子的更新次数cntc
5. 当前结点所有孙子的更新次数cntcc
6. 当前结点兄弟结点的更新次数cntb
7. 当前结点的度数deg

若已知了上面几个量，那么v处此时的答案为：
为了可以在O(1)的时间得到这些量，最好的方法就是直接维护这些量。
接下来的问题就在是否能高效地更新这些量呢。答案是可以的
首先是不会变的。预处理一次就可以得到。
开三个数组为a[N],b[N],c[N]。分别表示上面编号为3，4，5（也就是cnt,cntc,cntcc）的量，而编号为1，2的量可以通过保存每个结点的父亲结点fa[v]，用fa[v]和cnt[fa[v]]，cnt[fa[fa[v]]]来得到。
每次更新时同时更新相关量,时间为O(1)。
这么一个题就这样轻松愉快地解决了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=2e6+20;
const int INF=0x3f3f3f3f;
const LL MOD=19260817;
int n,m;
int deg[MAX_N];
int fa[MAX_N];
LL a[MAX_N],b[MAX_N],c[MAX_N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);
    cin>>n>>m;
    int v;
    for(int i=2;i<=n;i++){
        cin>>v;
        deg[v]++,deg[i]++;
        fa[i]=v;
    }
    int x;
    LL ans=0,ha=0;
    for(int i=1;i<=m;i++){
        cin>>x;
        a[x]++,b[fa[x]]++,c[fa[fa[x]]]++;
        ans=a[x]*(deg[x]+1)+b[x]*2+c[x];
        //cout<<ans<<" ";
        if(fa[x]!=0){
            ans+=2*a[fa[x]];
            ans+=b[fa[x]]-a[x];
            if(fa[fa[x]]!=0)ans+=a[fa[fa[x]]];
        }
        //cout<<ans<<endl;

        ha=(ans*i%MOD+ha)%MOD;
    }
    cout<<ha<<endl;

}