题意:
给你一棵树,最开始点权为。
次操作,每次将与一个点
树上距离
的所有点点权
,之后询问这些点修改后的点权和。
输出一个数,即这次操作的答案的
值,如果是第
次操作,这次操作结果为
,则这个
值加上
输出
值对
取模的结果。
数据范围:
题解:
本题由于时间卡的很死,故所有操作都需要进行。
是指
的儿子个数,
表示
的父亲。
指
被直接操作的次数,
指
的所有儿子被直接操作的次数,
指
的所有儿子的儿子被直接操作的次数。
对于一次取点进行的操作:
的父结点贡献为:
的
被直接操作次数,
的
的所有
被直接操作次数,以及
的父结点的父结点被直接操作次数
的贡献为:
的
被直接操作次数,
被直接操作次数,以及
的所有儿子被直接操作次数
的所有儿子贡献为:
的所有儿子因为
被直接操作而被间接操作的次数之和,
的所有儿子被直接操作次数,以及
的所有孙子被直接操作次数
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T> inline T Read() { T x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();} return x * f; } #define read() Read<int>() #define readl() Read<ll>() const int mod = 19260817; const int N = 1e5 + 10; int siz[N]; int fa[N]; int me[N], son[N], sson[N]; int main() { int n = read(), m = read(); for(int i = 2; i <= n; i++) { int x = read(); fa[i] = x, ++siz[x]; } int res = 0; for(int i = 1; i <= m; i++) { int x = read(); ++me[x]; if(fa[x]) ++son[fa[x]]; if(fa[fa[x]]) ++sson[fa[fa[x]]]; int ff = (me[fa[x]] + son[fa[x]] + me[fa[fa[x]]]) % mod; int mm = (me[fa[x]] + me[x] + son[x]) % mod; int ss = (1ll * siz[x] * me[x] % mod + son[x] + sson[x]) % mod; res = (1ll * (ff + mm + ss) % mod * i % mod + res) % mod; } printf("%d\n", res); return 0; }