点权和题解
题目分析:
一道以空间换时间的题目。关键在维护什么和怎么维护才能高效地得到答案。
通过仔细又认真地观察,再加上一点灵感,可以发现。每个点位置处地答案可以由这个点和与它距离小于等于2点的更新次数马上得到。
设有一个点,记为v,如果我们知道下面几个量,那么此时v处的答案可以在O(1)的时间马上得到:
- 当前结点父亲的父亲的更新次数cntff
- 当前结点的父亲的更新次数cntf
- 当前结点的更新次数cnt
- 当前结点所有儿子的更新次数cntc
- 当前结点所有孙子的更新次数cntcc
- 当前结点兄弟结点的更新次数cntb
- 当前结点的度数deg
若已知了上面几个量,那么v处此时的答案为:
为了可以在O(1)的时间得到这些量,最好的方法就是直接维护这些量。
接下来的问题就在是否能高效地更新这些量呢。答案是可以的
首先是不会变的。预处理一次就可以得到。
开三个数组为a[N],b[N],c[N]。分别表示上面编号为3,4,5(也就是cnt,cntc,cntcc)的量,而编号为1,2的量可以通过保存每个结点的父亲结点fa[v],用fa[v]和cnt[fa[v]],cnt[fa[fa[v]]]来得到。
每次更新时同时更新相关量,时间为O(1)。
这么一个题就这样轻松愉快地解决了。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAX_N=2e6+20; const int INF=0x3f3f3f3f; const LL MOD=19260817; int n,m; int deg[MAX_N]; int fa[MAX_N]; LL a[MAX_N],b[MAX_N],c[MAX_N]; int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); //freopen("1.in","r",stdin); cin>>n>>m; int v; for(int i=2;i<=n;i++){ cin>>v; deg[v]++,deg[i]++; fa[i]=v; } int x; LL ans=0,ha=0; for(int i=1;i<=m;i++){ cin>>x; a[x]++,b[fa[x]]++,c[fa[fa[x]]]++; ans=a[x]*(deg[x]+1)+b[x]*2+c[x]; //cout<<ans<<" "; if(fa[x]!=0){ ans+=2*a[fa[x]]; ans+=b[fa[x]]-a[x]; if(fa[fa[x]]!=0)ans+=a[fa[fa[x]]]; } //cout<<ans<<endl; ha=(ans*i%MOD+ha)%MOD; } cout<<ha<<endl; }