Codeforces - 500D. New Year Santa Network - 树形dp、数学、思维

New Year Santa Network

题目链接

分类：树形dp、思维、数学

1.题意概述

• 给你由n个节点构成的树，有(n-1)条边，随机选取其中三个节点a、b、c，定义$dist=dis(a,b)+dis(b,c)+dis(c,a)$，现在有q次操作，每次选取某条边，使得它的边权由原先的$w_i$变成$l_i$，问你每次操作以后的期望$E(dist)$是多少？

2.解题思路

• 根据期望性质$E[dis(a,b)+dis(b,c)+dis(c,a)]=E[dis(a,b)]+E[dis(b,c)]+E[dis(c,a)]$
  
  • 方法一：按边考虑，n个点中任意取3个点的取法是$\textrm{C}_n^3$种，我们考虑每条边出现的概率。如果我们选定边$ab$，那么第三个点$c$就在剩下的$(n-2)$个点中取，也就是边$ab$会出现$(n-2)$次，假设这条边下面的儿子个数为$son[x]$，而经过这条边的种类数$son[x] · (n-son[x])$，所以最终概率为$p_{ab}=\frac{son[x](n-son[x])(n-2)}{C_n^3}$，而总的期望就是$E(dist)=\sum E[dis(i,j)]=p_{ij}· w_{ij}$！而统计儿子个数我们可以通过树形dp跑一遍dfs就可以求得，而每条边的权值的变动，只会影响$w_{ij}$，根据期望性质，我们可以先求得边尚未改变的期望，然后减去$(l_{ij}-w_{ij})·p_{ij}$就是结果！
  • 方法二：按点考虑，画图容易发现，树中任意选三点构成合法路线，某条边一定会经过两次，那么我们对于这条边两侧的点考虑，假设左侧有$a$个点，右侧有$b$个点，那么这三个点的选法有$\textrm{C}_a^2·\textrm{C}_b^1+\textrm{C}_a^1·\textrm{C}_b^2$种，结果就是$\frac{2(\textrm{C}_a^2·\textrm{C}_b^1+\textrm{C}_a^1·\textrm{C}_b^2)}{\textrm{C}_n^3}$，下面做法和方法一类似。

3.AC代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 100010
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
#define N 1111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
    int to, id;
    node(int a, int b) { to = a; id = b; }
};
vector<node> g[maxn];
double p[maxn];
int son[maxn], w[maxn];
void dfs(int u, int fa, int pid, const int &n)
{
    son[u] = 1;
    int sz = g[u].size();
    for (int i = 0; i < sz; i++)
    {
        int v = g[u][i].to;
        int id = g[u][i].id;
        if (v != fa)
        {
            dfs(v, u, id, n);
            son[u] += son[v];
        }
    }
    p[pid] = 6.0 * son[u] * (n - son[u]) / n / (n - 1);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
#endif
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d%d", &a, &b, &w[i]);
        g[a].push_back(node(b, i));
        g[b].push_back(node(a, i));
    }
    dfs(1, -1, 0, n);
    double ans = 0;
    for (int i = 1; i < n; i++)
        ans += w[i] * p[i];
    scanf("%d", &m);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int delta = w[a] - b;
        ans -= delta * p[a];
        printf("%.12f\n", ans);
        w[a] -= delta;
    }
#ifndef ONLINE_JUDGE
    long _end_time = clock();
    printf("time = %ld ms.", _end_time - _begin_time);
#endif
    return 0;
}