题解：
我试图去遍历邻接表（以为是水题），结果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;
}
京公网安备 11010502036488号