题意:
给你一棵树,最开始点权为。
次操作,每次将与一个点
树上距离
的所有点点权
,之后询问这些点修改后的点权和。
输出一个数,即这次操作的答案的
值,如果是第
次操作,这次操作结果为
,则这个
值加上
输出
值对
取模的结果。
数据范围:
题解:
本题由于时间卡的很死,故所有操作都需要进行。
是指
的儿子个数,
表示
的父亲。
指
被直接操作的次数,
指
的所有儿子被直接操作的次数,
指
的所有儿子的儿子被直接操作的次数。
对于一次取点进行的操作:
的父结点贡献为:
的
被直接操作次数,
的
的所有
被直接操作次数,以及
的父结点的父结点被直接操作次数
的贡献为:
的
被直接操作次数,
被直接操作次数,以及
的所有儿子被直接操作次数
的所有儿子贡献为:
的所有儿子因为
被直接操作而被间接操作的次数之和,
的所有儿子被直接操作次数,以及
的所有孙子被直接操作次数
#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;
} 
京公网安备 11010502036488号