存在一棵以
首先一个比较重要的性质就是
不难想到 DP,令
朴素的转移十分显然,即在其儿子里找到两个层高为
考虑到我们每次询问都是增加一个节点,如此的转移方式复杂度显然是不正确的,考虑优化。不难想到这个式子可以转化为从和平方里去除平方和,即:
于是这个东西就可以支持
最终的答案即为
所以每次修改都是
xxxxxxxxxx
1101
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27struct Edge{
28 Edge* nxt;
29 int to;
30 OPNEW;
31}ed[610000];
32ROPNEW(ed);
33Edge* head[310000];
34
35ll qpow(ll a, ll b){
36 ll ret(1), mul(a);
37 while(b){
38 if(b & 1)ret = ret * mul % MOD;
39 b >>= 1;
40 mul = mul * mul % MOD;
41 }return ret;
42}
43
44int N;
45int mxdep;
46int inv2;
47int dep[310000];
48int fa[310000];
49ll ans(0);
50ll sum[310000][21], sum2[310000][21];
51
52ll DP(int p, int i){
53 if(i == 1)return 1;
54 return ((sum[p][i] * sum[p][i] % MOD - sum2[p][i]) % MOD + MOD) % MOD * inv2 % MOD;
55}
56void dfs(int p = 1, int fa = 0){
57 dep[p] = dep[fa] + 1;
58 for(auto i = head[p]; i; i = i->nxt)
59 if(SON != fa)dfs(SON, p);
60}
61
62int main(){
63 // freopen("in.txt", "r", stdin);
64 // freopen("out.txt", "w", stdout);
65 inv2 = qpow(2, MOD - 2);
66 N = read();
67 if(N == 1)printf("1\n"), exit(0);
68 mxdep = (int)log2(N);
69 for(int i = 2; i <= N; ++i){
70 fa[i] = read();
71 head[i] = new Edge{head[i], fa[i]};
72 head[fa[i]] = new Edge{head[fa[i]], i};
73 }dfs();
74 for(int cp = 1; cp <= N; ++cp){
75 if(dep[cp] <= mxdep){
76 sum[cp][1] = sum2[cp][1] = 1;
77 ll cnt(1), cur(cp), lst(-1), lstDP(0);
78 while(cur != 1){
79 lst = cur;
80 cur = fa[cur], ++cnt;
81 ll tmp = DP(cur, cnt);
82 (((sum[cur][cnt] -= lstDP) %= MOD) += MOD) %= MOD;
83 (((sum2[cur][cnt] -= lstDP * lstDP % MOD) %= MOD) += MOD) %= MOD;
84 lstDP = tmp;
85 (sum[cur][cnt] += DP(lst, cnt - 1)) %= MOD;
86 (sum2[cur][cnt] += DP(lst, cnt - 1) * DP(lst, cnt - 1) % MOD) %= MOD;
87 }
88 }ans = 0;
89 for(int i = 1; i <= mxdep; ++i)(ans += DP(1, i)) %= MOD;
90 printf("%lld\n", ans);
91 }
92 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93 return 0;
94}
95
96template < typename T >
97inline T read(void){
98 T ret(0);
99 int flag(1);
100 char c = getchar();
101 while(c != '-' && !isdigit(c))c = getchar();
102 if(c == '-')flag = -1, c = getchar();
103 while(isdigit(c)){
104 ret *= 10;
105 ret += int(c - '0');
106 c = getchar();
107 }
108 ret *= flag;
109 return ret;
110}
update-2023_01_03 初稿