Codeforces 500D(期望+组合数+树边贡献DFS)

Codeforces 500D
题意:给一棵有$n$个节点的树,有$q$次操作,每次操作将改变某条边边权,问改变后,从$n$个点中等概率任取三点,将这三点用最短路连接起来的距离和$d(a,b)+d(a,c)+d(b,c)$的数学期望值。

树上计数一般这种整棵树计数的就是边点贡献。这里明显边贡献。算出每条边每次要计算几次即可。因为维修道路并不会影响这些次数。
对于一条边,他左边有$x$个点,右边则有$n-x$个点,记为$y$。那么通过这条边的方案数(左边选2个,右边选1个或者反之)为$yC^2_x+xC^2_y$,化简后得$(n-x)(n-2)x$,就可以这样每个点计算然后除以$C_n^3$即可。或者直接除,化简得$\frac{6(n-x)x}{n(n-1)}$,然后只要每个点记录$6(n-x)x$,然后询问时除以$n(n-1)$即可。

知识点:树上整棵数计数/最优值等路径覆盖问题和边贡献有关。本题与CF 701思想类似。

如果写暴力直接枚举三元组然后 LCA 求两点距离统计即可,复杂度$O(n^3logn)$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MAXN = 100000 + 5;
struct edge {
LL v, w, no;
}ed[MAXN * 2ll];
LL n, q, en, siz[MAXN], tms[MAXN], ans;
std::vector<LL > G[MAXN];
inline void ins(LL x, LL y, LL w, LL no) {
ed[++en] = (edge){y, w, no}, G[x].push_back(en);
ed[++en] = (edge){x, w, no}, G[y].push_back(en);
}
void dfs(LL u, LL pa) {
siz[u] = 1ll;
for (LL i = 0ll; i < (LL)G[u].size(); i++) {
edge &e = ed[G[u][i]];
if (e.v != pa) dfs(e.v, u), tms[e.no] += 6ll * (n - siz[e.v]) * siz[e.v], siz[u] += siz[e.v];
}
}
void clean() {
ms(tms, 0ll), ans = en = 0ll;
}
int solve() {
clean();
for (LL a, b, l, i = 1ll; i < n; i++) scanf("%lld%lld%lld", &a, &b, &l), ins(a, b, l, i);
dfs(1ll, 0ll);
for (LL i = 1ll; i < n; i++) ans += tms[i] * ed[i * 2ll].w;
scanf("%lld", &q);
while (q--) {
LL r, w; scanf("%lld%lld", &r, &w);
ans -= tms[r] * ed[r * 2ll].w, ed[r * 2ll].w = w, ans += tms[r] * ed[r * 2ll].w;
printf("%.8f\n", (db)ans / (db)n / (db)(n - 1ll));
}
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}

------ 本文结束 ------