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)$

#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;
}