这题的标签是倍增。。。这真的算倍增的吗。
由于题中所给是父亲节点,那么可以想办法将儿子节点带来的贡献转化成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; }