Description
给你一棵以点 1 为根的有根树，定义删掉一条边的代价为当前儿子节点的子树大小，问你将所有边删完后的期望代价和。
评测时自动启动 O2 优化。
Solution
考虑将一个极大子树产生的贡献绑在这个子树的根上。
发现如果删了一个点，再删掉了某一条它到根节点的简单路径上的边的话，那么总贡献应该就是就是后删掉的那条边的儿子节点的子树大小。
即如果一个点 $i$ 能够给出 $size_i$ 的贡献，那么当且仅当从点 $i$ 到根节点的边上的点没有再给出贡献。
其中 $size_i$ 表示的是点 $i$ 的子树大小。
因为从点 $i$ 到根节点的边上的点（不包括点 $i$）一共有 $dep_i$ 个，所以给出贡献的概率是 $\dfrac{1}{dep_i}$，所以最终的答案就是：
其中 $dep_i$ 表示的是点 $i$ 的深度，其中 $dep_1 = 0$。
因为这题卡常，所以最好线性预处理逆元。
其他神奇的卡常技巧见代码。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<cstdio>
using ll = long long;
constexpr ll mod = 1000000007;
inline ll Read()
{
char c;
for (c = getchar(); c > '9' || c < '0'; c = getchar());
ll ans = static_cast<ll>(c) - '0';
for (c = getchar(); c >= '0' && c <= '9'; ans = (ans * 10) + (static_cast<ll>(c) - '0'), c = getchar());
return ans;
}
struct Node
{
ll father, size, depth, son_count;
Node() :son_count(0), father(-1), size(1), depth(0) {}
}nod[2000002];
ll que[2000002], inv[2000002];
int main()
{
const ll n = Read();
for (ll i = 2; i <= n; ++i)
{
nod[i].father = Read();
++nod[nod[i].father].son_count;
}
ll head = 0, tail = 0;
for (ll i = 1; i <= n; ++i)
{
if (nod[i].son_count == 0)
{
que[tail++] = i;
}
}
while (head < tail)
{
const ll& from = que[head++], & to = nod[from].father;
if (to != -1)
{
nod[to].size += nod[from].size;
if ((--nod[to].son_count) == 0)
{
que[tail++] = to;
}
}
}
ll size_inv = 0;
for (tail -= 2; tail >= 0; --tail)
{
const ll& pos = que[tail];
nod[pos].depth = nod[nod[pos].father].depth + 1;
if (nod[pos].depth > size_inv)
{
size_inv = nod[pos].depth;
}
}
inv[1] = 1;
for (ll i = 2; i <= size_inv; ++i)
{
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
ll ans = 0;
for (ll i = 2; i <= n; ++i)
{
ans += inv[nod[i].depth] * nod[i].size % mod;
}
printf("%lld", ans % mod);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#define mod 1000000007
#define maxN 2000010
struct Edge{ int y, g; } b[maxN];
int len = 0, R = 0;
int size[maxN], dep[maxN], dl[maxN], fa[maxN], h[maxN];
long long inv[maxN];
int max (int x, int y)
{
return x > y ? x : y;
}
int read ()
{
int x = 0;
char c = getchar();
while(c < '0' || c > '9')
{
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
void ins (int x, int y)
{
len++;
b[len].y = y;
b[len].g = h[x];
h[x] = len;
}
void bfs (int S)
{
int head = 1, tail = 2;
dl[head] = S;
while(head < tail)
{
int x = dl[head++];
for(register int i = h[x];i;i = b[i].g)
{
dep[dl[tail++] = b[i].y] = dep[x] + 1;
R = max(R, dep[b[i].y]);
}
}
for(register int i = tail - 1;i > 1; i--)
{
size[fa[dl[i]]] += size[dl[i]];
}
}
int main ()
{
int n = read();
for(register int i = 2;i <= n; i++)
{
size[i] = 1;
ins(fa[i] = read(), i);
}
int root = 1;
bfs(root);
inv[0] = 0, inv[1] = 1;
for(register int i = 2;i <= R; i++)
{
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
long long Ans = 0;
for(register int i = 2;i <= n; i++)
{
Ans += size[i] * inv[dep[i]] % mod;
}
printf("%lld", Ans % mod);
return 0;
}
|