题解:
由题意可知,每次操作后的点权和由三部分组成:被选中操作的点的贡献,被选择操作点的子节点的贡献,被选择操作点父亲节点的贡献
故我们可以开三个数组分别维护这些贡献,每次操作完后进行跟新,再将这三种贡献加起来便可以最终计算得到hash值
定义:
self[x]:x被选中操作的次数
son[x]:x子节点由于自身被选中及其孩子节点被选中的贡献
father[x]:x作为父节点由于其孩子节点被选中造成的贡献
故每次操作,假设选择x;
首先x自身被选中,self[x]++;
接着由于x被选择,x的父亲节点如果存在,那么x也会对其造成影响:if(fa[x]) father[fa[x]]++;
由于x被选中,如果x的父亲节点存在,那么其父亲节点的字节点贡献也会加1:if(fa[x]) son[fa[x]]++;
最后如果x节点的父亲节点存在,x会对其父亲节点造成贡献,所以x的父亲节点值会增长,这样比如会对x父亲节点的父亲节点造成影响:
if(fa[fa[x]]) son[fa[fa[x]]]++;
接着计算贡献值:
被选中节点的贡献:自己被选中的次数,其父节点的贡献,其子节点对自己的贡献
即 self[x]+self[fa[x]]+father[x]
被选中节点父节点的贡献:父节点被选中的次数+父节点的字节点对父节点的贡献次数+父节点的父节点被选择次数
即:self[fa[x]]+father[fa[x]]+self[fa[fa[x]]]
最后计算被选择点的子节点的贡献:x子节点由于自身被选中及其孩子节点被选中的贡献+x被选中对子节点造成的贡献
即:son[x]+g[x].size()*self[x]
#include<bits/stdc++.h> using namespace std; int n,m; int mod=19260817; int fa[100005]; int self[100005];//对自身操作的次数 int father[100005];//作为父节点被子节点操作的次数 int son[100005];//其儿子节点的贡献 vector<int> g[100005]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<n;i++) { cin>>fa[i+1]; g[fa[i+1]].push_back(i+1);//将子节点加入父节点的容器 } long long hash=0; int x; for(int i=1;i<=m;i++) { cin>>x; self[x]++;//自身操作次数+1 if(fa[x]) son[fa[x]]++;//父节点的子节点贡献+1 if(fa[fa[x]]) son[fa[fa[x]]]++;//爷爷的儿子节点贡献+1 if(fa[x]) father[fa[x]]++;//对其父节点的贡献+1 long long sum=0; sum+=self[x]+self[fa[x]]+father[x];//加上自身贡献度 sum+=father[fa[x]]+self[fa[x]]+self[fa[fa[x]]];//父亲贡献度 sum+=son[x]+self[x]*g[x].size();//儿子贡献 hash=(hash+sum*i%mod)%mod; } cout<<hash<<endl; }