忘了写题解，但总觉得要写点啥，所以就有了这篇题集。

A – Tree

是个网络流啊，GG。

六中的神仙提出了一种很出色的方法：将树上的边按深度大的往深度小的连，并且流量为\(1\)，费用为\(0\)；对于每一种路径，按深度大的往深度小的连，流量为\(1\)费用为\(c_i\)，并且让源点向深度大的点连边，流量为\(1\)费用为\(0\)，深度小的点向汇点连边，流量为\(1\)费用为\(0\)。

我们可以求出最小费用最大流，然后这最小费用就相当于最小割，我们可以对路径贡献求和再减去费用得到答案。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, head[MAX_N], current, dep[MAX_N], T, START, END, deg[MAX_N];
int pre[MAX_N], flow[MAX_N];
ll dist[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt, weight, cost;
} edges[MAX_N << 2];

struct path
{
    int u, v, d;
} paths[MAX_N];

vector<edge> G[MAX_N];

void fileIO()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
}

inline char nc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

void addpath(int src, int dst, int weight, int cost)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, edges[current].cost = cost;
    head[src] = current++;
}

void addtube(int src, int dst, int weight, int cost)
{
    addpath(src, dst, weight, cost);
    addpath(dst, src, 0, -cost);
}

bool spfa_min(int src)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    memset(flow, 0, sizeof(flow));
    queue<int> q;
    q.push(src), vis[src] = true, dist[src] = 0;
    flow[src] = 0x3f3f3f3f;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].cost && edges[i].weight > 0)
            {
                dist[edges[i].to] = dist[u] + edges[i].cost;
                flow[edges[i].to] = min(edges[i].weight, flow[u]);
                pre[edges[i].to] = i;
                if (!vis[edges[i].to])
                    q.push(edges[i].to), vis[edges[i].to] = true;
            }
    }
    return flow[END] != 0;
}

ll mcmf()
{
    ll ans = 0;
    while (spfa_min(START))
    {
        ans += dist[END] * flow[END];
        int pt = END, i = pre[pt];
        while (pt != START)
        {
            edges[i].weight -= flow[END], edges[i ^ 1].weight += flow[END];
            pt = edges[i ^ 1].to, i = pre[pt];
        }
    }
    return ans;
}

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (int i = 0, siz_ = G[u].size(); i < siz_; i++)
        if (G[u][i].to != fa)
            dfs(G[u][i].to, u), addtube(G[u][i].to, u, G[u][i].weight, 0);
}

void initialize()
{
    memset(head, -1, sizeof(head)), current = 0;
    for (int i = 1; i <= n; i++)
        G[i].clear();
    START = 0, END = n + 1, memset(deg, 0, sizeof(deg));
}

int main()
{
    T = read();
    while (T--)
    {
        n = read(), m = read();
        initialize();
        for (int i = 1, u, v, w; i <= n - 1; i++)
        {
            u = read(), v = read(), w = read();
            G[u].push_back(edge{v, 0, w, 0}), G[v].push_back(edge{u, 0, w, 0});
        }
        dfs(1, 0);
        ll answer = 0;
        for (int i = 1, u, v, w; i <= m; i++)
        {
            u = read(), v = read(), w = read();
            if (dep[u] < dep[v])
                swap(u, v);
            answer += w, addtube(u, v, 1, w);
            addtube(START, u, 1, 0), addtube(v, END, 1, 0);
        }
        printf("%lld\n", answer - mcmf());
    }
    return 0;
}

B – Dice

这题还蛮有趣的，期望部分比较板但方差的部分还真的挺难的。

先考虑期望的30分，我们设置\(f[i][j]\)为前\(i\)次中最后一次选\(j \in [1, 6]\)的概率，设置\(g[i][j]\)为相应的期望。那么，转移的时候需要注意概率并不是直接乘上\(p_j\)，而是需要考虑重复投掷的情况：

\[ \sum_{t = 0}^{\infty} p_j p_k^t = \frac{p_j}{1 – p_k} \]

这其实是个几何级数，把\(p_j\)提出来之后套公式即可。我们得到了转移时的概率。那么，期望也就很好求了：

\[ g[i][j] = \sum_{k = 1}^6 [k \neq j] g[i – 1][k] \frac{p_j}{1 – p_k} + j \cdot f[i][j] \]

30 分到手。那么，我们来看方差的部分，列式展开：

\[ (ans – E[ans])^2 = ans^2 – 2ansE[ans] + E[ans]^2 \]

由于\(E[ans] = p_{ans} \cdot ans\)，那么自然的，\(ansE[ans] = p_ans \cdot ans^2 = E[ans]^2\)，就剩下了：

\[ ans^2 – E[ans]^2 \]

第二个部分直接平方即可；第一个部分比较麻烦，因为涉及到平方的期望。我们仍可以设置\(s[i][j]\)，那么转移则是：

\[ s[i][j] = \sum_{k = 1}^6 [j \neq k] s[i – 1][k] \frac{p_j}{1 – p_k} + j^2 f[i][j] + 2j(g[i][j] – f[i][j]\cdot j) \]

其中比较特别的是\((g[i][j] – f[i][j] \cdot j)\)，回顾上面的式子，发现这个其实就是上一轮转移到当前状态的所有线性级别的期望（有点绕，也就是说都一次项）。

卡精度就把\(ans\)换成\(\frac{ans}{n}\)，然后就可以过了。（有点玄学）

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;
typedef long double ld;

int n;
ld pi[10], f[MAX_N][7], g[MAX_N][7], s[MAX_N][7];

void fileIO()
{
    freopen("dice.in", "r", stdin);
    freopen("dice.out", "w", stdout);
}

int main()
{
    // fileIO();
    for (int i = 1; i <= 6; i++)
        cin >> pi[i], f[1][i] = pi[i];
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= 6; j++)
            for (int k = 1; k <= 6; k++)
                if (j != k)
                    f[i][j] += f[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 6; j++)
        {
            for (int k = 1; k <= 6; k++)
                if (j != k)
                    g[i][j] += g[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
            g[i][j] += f[i][j] * j;
        }
    ld ans1 = 0, ans2 = 0;
    for (int i = 1; i <= 6; i++)
        ans1 += g[n][i];

    ld tmp = ans1 / n;
    for (int i = 1; i <= 6; i++)
        f[1][i] = pi[i] * (i - tmp), g[1][i] = pi[i], s[1][i] = (i - tmp) * (i - tmp) * pi[i];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= 6; j++)
        {
            f[i][j] = g[i][j] = 0;
            ld tmp_sum = 0;
            for (int k = 1; k <= 6; k++)
                if (j != k)
                {
                    f[i][j] += f[i - 1][k] * pi[j] / (1.0 - pi[k]), tmp_sum += 1.0 * pi[j] * g[i - 1][k] / (1 - pi[k]);
                    s[i][j] += s[i - 1][k] * ld(pi[j] / (1.0 - pi[k]));
                }
            s[i][j] += 2.0 * (j - tmp) * f[i][j] + tmp_sum * (j - tmp) * (j - tmp), f[i][j] += tmp_sum * (j - tmp);
            g[i][j] = tmp_sum;
        }
    for (int i = 1; i <= 6; i++)
        ans2 += s[n][i];
    printf("%.10Lf\n%.10Lf\n", ans1, ans2);
    return 0;
}