题解-AT_abc314_f

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

初始时有 $n$ 个团队，每个团队 $i$ 都只有一个编号为 $i$ 的人，现在有 $n-1$ 场比赛，比赛的胜率通过如下方法得出：

设 $i,j$ 两团队进行比赛，人数分别为 $s_i,s_j$，则双方的胜率分别为 $\frac{s_i}{s_i+s_j},\frac{s_j}{s_i+s_j}$。

在比赛完之后，两个团队的人便会合并成一个团队（不打不相识？），现在要求你输出所有比赛完之后每个人期望赢几场比赛。

保证输入样例合法，不存在同一个团队比赛的情况。

解题思路

这个合并操作让我想起了并查集和树。

我们将一个人获胜的期望定义为在这棵并查集森林（当然最后是树）中，自己这个点的和根节点连线的权值和。

权值如何定义呢？自然是比赛时双方的胜率。

但是我们模拟两下就会发现一个问题：这样累计会让下方的节点期望错误地加上上方节点的期望导致偏高，那我们减回去就行了。

至于节点上下的问题，这个其实不重要，但是我写了启发式合并怕被卡。

#include <stdio.h>

typedef long long i64;
const i64 mod = 998244353, maxn = 400007;

i64 pow(i64 x, i64 p);

struct modint
{
    i64 x;
    modint(i64 x_ = 0)
    {
        if (x_ < 0)
            x = (x_ % mod + mod) % mod;
        else if (x_ >= mod)
            x = x_ % mod;
        else
            x = x_;
    }
    modint inv() { return pow(x, mod - 2); }
    modint operator+=(modint b);
    modint operator-=(modint b);
    modint operator*=(modint b);
    modint operator/=(modint b);
};

modint operator+(modint a, modint b);
modint operator-(modint a);
modint operator-(modint a, modint b);
modint operator*(modint a, modint b);
modint operator/(modint a, modint b);
modint pow(modint x, i64 p);
bool operator==(modint a, modint b);

int fa[maxn], size[maxn], kzy[maxn];
modint val[maxn];

int findf(int index)
{
    return fa[index] == index ? index : findf(fa[index]);
}

modint tj(int index)
{
    if (fa[index] == index)
        return val[index];
    return tj(fa[index]) + val[index];
}

void merge(int u, int v)
{
    u = findf(u);
    v = findf(v);
    if (size[u] > size[v])
        u ^= v ^= u ^= v;
    val[v] += modint(size[v]) / modint(size[u] + size[v]);
    val[u] -= val[v]; // 像上文说的那样，这里需要减去上面的值，类似于差分的思想
    val[u] += modint(size[u]) / modint(size[u] + size[v]);
    fa[u] = v;
    size[v] += size[u];
}

int n, u, v;

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        fa[i] = i, size[i] = 1, val[i] = 0;

    for (int i = 1; i < n; i++)
        scanf("%d%d", &u, &v),
            merge(u, v);

    for (int i = 1; i <= n; i++)
        printf("%lld ", tj(i));
    return 0;
}