牛客——点权和

(4个月前好像见过这个题?)

思路:

考虑每次修改后对答案的贡献,对于一个点来说,考虑这个点会影响到哪些点。

考虑只进行一次更新的情况:首先,就是本身,本身的节点值对答案的贡献是度数+1,因为本身的点权会更新,邻接点也会更新;再者,就是他的父节点,父节点对答案的贡献是2,因为在这个过程中本身和父节点的点权都+1了;最后就是他父节点的父节点,因为父节点的更新使得爷爷节点对答案的贡献为1;再考虑他的父节点的其他子节点对他的贡献,这时候要注意去重。

多次的话,我们只需要维护cnt1[x]表示x的操作次数,cnt2[x]表示x的父节点的子节点(即x的兄弟)的操作次数和res[x]表示答案,然后计算对应贡献即可。

代码:

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
#define modl 19260817*19890604-19491001
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=1e6+7,mod=19260817;

ll n,m,fa[maxn],d[maxn];
ll cnt1[maxn],cnt2[maxn],res[maxn];

int main(){
    n=read(),m=read();
    for(int i=2;i<=n;i++){
        fa[i]=read();
        d[i]++;d[fa[i]]++;
    }
    ll sum=0;
    for(int i=1;i<=m;i++) {
        int x=read();
        res[x]=(res[x]+d[x]+1)%mod;
        if(fa[x]){
            res[fa[x]]=(res[fa[x]]+2)%mod;
            cnt2[fa[x]]=(cnt2[fa[x]]+1)%mod;
        }
        if(fa[fa[x]]){
            res[fa[fa[x]]]=(res[fa[fa[x]]]+1)%mod;
        }
        cnt1[x]=(cnt1[x]+1)%mod;
        ll tmp=0;
        if(fa[x]){
            tmp=(tmp+2*cnt1[fa[x]]%mod)%mod;
            if(tmp<0) tmp+=mod;
            tmp=(tmp+(cnt2[fa[x]]-cnt1[x]))%mod;
            if(tmp<0) tmp+=mod;
        }
        if(fa[fa[x]]) tmp=(tmp+cnt1[fa[fa[x]]])%mod;
        tmp=(tmp+res[x])%mod;
        sum=(sum+i*tmp%mod)%mod;
    }
    out(sum);
    return 0;
}