NC14393 基础树上问题

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

最初看到题目说父节点序号一定小还以为要搞什么大动作用树剖……结果想多了。
在树上相距小于1的店就是自己、父亲、孩子们。为了O（1）计算每次这些点的权值和，我们记录三个数组（看代码,,cnt123），分别表示x被选中次数，x的孩子们被选中的次数和，x的孙子们被选中的次数和。这样val[x]=cnt1[x]+cnt1[fa[x]]+cnt2[x]，val[fa[x]]方法同上，val[sons]=cnt1[x]*sons.size+cnt2[x]+cnt3[x]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+4;

int fa[maxn],siz[maxn];
ll cnt1[maxn],cnt2[maxn],cnt3[maxn];
//cnt1表示i节点被选中的次数，cnt2表示i的孩子们被选中的总次数，cnt3表示i的孙子们的被选次数
const int mod=19260817;
inline ll calc(int x){
    //计算节点x的权值
    return (((fa[x]?cnt1[fa[x]]:0)+cnt1[x])%mod+cnt2[x])%mod;
}


inline ll read(){
    ll v=0, f=1;
    char c=getchar();
    while(c<48||57<c){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(48<=c&&c<=57)
        v=v*10+c-48, c=getchar();
    return v*f;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int f,i=2;i<=n;i++){
        f=read();
        fa[i]=f;
        siz[f]++;
    }
    ll ans=0;
    for(ll i=1,x;i<=m;i++){
        x=read();
        cnt1[x]++;
        if(fa[x]>0){
            cnt2[fa[x]]++;
            if(fa[fa[x]]>0)
                cnt3[fa[fa[x]]]++;
        }
        ans=(ans+(i*calc(x))%mod)%mod;
        if(fa[x]>0)
            ans=(ans+(calc(fa[x])*i)%mod)%mod;
        ans=(ans+i*(siz[x]*cnt1[x]%mod+cnt2[x]+cnt3[x])%mod)%mod;
    }
    cout<<ans<<endl;
}