[ABC314F] A Certain Game 题解

FFTotoro · 2023-08-13 12:14:24 · 题解

考虑合并队伍的性质，显然一路合并上去这个结构是个树。用启发式合并的思想，每次先把 p_i,q_i 找个并查集里面的祖先，然后把大小比较小的那个集合向大集合连边（大集合的祖先现在变成小集合的祖先的父亲）。

最后对于每个点跳父亲查找、累加贡献即可。记得每次合并两个集合的时候大集合要减去小集合的贡献，因为跳父亲的时候会被算一次而它本来不该被算进去。

实现借助了 AtCoder Library 的并查集和 modint。

放代码：

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using mint=atcoder::modint998244353;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> p(n,-1);
  vector<mint> c(n);
  atcoder::dsu d(n);
  for(int i=1;i<n;i++){
    int u,v; cin>>u>>v; u--,v--;
    u=d.leader(u),v=d.leader(v);
    int a=d.size(u),b=d.size(v);
    if(u!=d.merge(u,v))swap(u,v),swap(a,b);
    c[u]+=mint(a)/(a+b),c[v]+=mint(b)/(a+b)-c[u],p[v]=u;
  } // 连边过程
  vector<bool> b(n);
  function<void(int)> dfs=[&](int u){
    if(!b[u])if(b[u]=true;~p[u])dfs(p[u]),c[u]+=c[p[u]];
  }; // 继承父亲
  for(int i=0;i<n;i++)
    dfs(i),cout<<c[i].val()<<' ';
  return 0;
}