NC14393 点权和
点权和
https://ac.nowcoder.com/acm/problem/14393
点权和
题目地址：
基本思路:
这题的题意好像说的不是很明白，其实意思应该是第次操作先将与x树上距离<=1的点点权加一后，
再将这些与x树上距离<=1的点的点权之和作为这次操作的结果乘以记录进最终结果。
所以根据题意，我们设三个数组变量,
,
分别表示，当前点被操作次数,当前点孩子节点被操作次数,当前点孙子节点被操作次数。
对于每次的操作,我们先更新这三个数组变量的值然后再利用这三个变量计算这次操作的结果,
每次操作后的结果应当是自己，父亲，和所有孩子的点权之和，那么我们分别计算贡献：
此时父亲节点的点权贡献为：,
当前节点自己的点权贡献为：,
当前节点孩子的点权贡献为：,
那么通过上面三个部分，我们就能计算出每次操作后的结果乘以操作序号计算答案就行了。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
const int mod = 19260817;
int n,m,sz[maxn];
//a记录当前点被操作次数，b记录当前点孩子节点被操作次数,c记录当前点孙子节点被操作次数;
int fa[maxn],a[maxn],b[maxn],c[maxn];
signed main() {
n = read(), m = read();
rep(i, 2, n) {
int x = read();
sz[x]++; fa[i] = x;
}
int ans = 0;
rep(i, 1, m) {
int x = read();
a[x]++;
if (fa[x] != 0) b[fa[x]]++;
if (fa[fa[x]] != 0) c[fa[fa[x]]]++;
int par = (a[fa[x]] + b[fa[x]] + a[fa[fa[x]]]) % mod; // 父亲的权值贡献;
int my = (a[fa[x]] + a[x] + b[x]) % mod; // 自己的权值贡献;
int son = (sz[x] * a[x] % mod + b[x] + c[x]) % mod; // 所有孩子的权值贡献;
int res = (par + my + son) % mod;
ans = (ans + res * i % mod) % mod;
}
print(ans);
return 0;
}
