这题的标签是倍增。。。这真的算倍增的吗。
由于题中所给是父亲节点,那么可以想办法将儿子节点带来的贡献转化成x作为父亲节点时儿子所带来的贡献。这样通过记录每一个点作为自身、父亲、爷爷。所接受的影响。
三个关键数组:
tag[x]:x节点改变对自身的改变。
ftag[x]:x节点作为父亲时收到儿子的影响改变
gtag[x]:x节点作为爷爷收到孙子节点的影响改变。
in[x]:记录x节点的所有临界点的个数。
为什么只持续到爷爷。因为一个数改变对于父亲节点有加一的影响,而父亲节点加一会让爷爷节点计算的结果也加一。所以影响持续到了爷爷节点。
计算下方的贡献:
当儿子作为x被改变之后他作为儿子的父亲受到影响:ftag[x]*2
当孙子作为x被改变:gtag[x]
所以向下的总和:2*ftag[x]+gtag[x]
计算向上产生的贡献:
父亲节点的影响:tag[fa[x]]*2
爷爷节点产生的影响:tag[fa[fa[x]]]
父亲节点的其他儿子也会改变父亲节点的值从而对结果产生影响:ftag[fa[x]]-tag[x]
总和:tag[fa[x]]*2+tag[fa[fa[x]]]+ftag[fa[x]]-tag[x]
然后x节点自身的改变也会产生贡献:(in[x]+1)*tag[x]
#include <bits/stdc++.h>

using namespace std;
// #define int long long
typedef long long ll;
const int maxn = 100000+10;
const int mod = 19260817;
//记录书
int fa[maxn];
//记录树临界节点的个数
int in[maxn];
//因为影响最多到爷爷
ll tag[maxn];//记录针对自身的操作
ll ftag[maxn];//记录自身作为父亲的改变
ll gtag[maxn];//记录自身作为爷爷的改变。

signed main() {
    int n, m;
    scanf("%d %d", &n, &m);
    fa[1] = 0;
    for (int i=2;i<=n;i++) {
        scanf("%lld", &fa[i]);
        in[i]++;in[fa[i]]++;
    }
    ll x, ans, num = 1, as = 0;
    //开始操作
    while (m--) {
        scanf("%lld", &x);
        ans = 0;
        //对其自身
        tag[x]++;
        //如果存在父亲
        if (fa[x] != x) {
            ftag[fa[x]]++;
            ans = (ans + ((2*ftag[x])+gtag[x]))%mod;
            ans = (ans + ((tag[fa[x]]*2)+(ftag[fa[x]]-tag[x])))%mod;
        }
        //如果存在爷爷
        if (fa[fa[x]]) {
            gtag[fa[fa[x]]]++;
            ans = (ans+tag[fa[fa[x]]])%mod;
        }
        ans = (ans+(in[x]+1)*tag[x])%mod;
        as = (as%mod+(ans*num)%mod)%mod;
        num++;
    }
    cout<<as%mod<<endl;
    
    return 0;
}