题意
有 n 支队伍进行比赛，起初，第 i 支队伍只有选手 i 一个人。总共要进行 n-1 场比赛，每次给出 p 和 q，意为让 p 所在的队伍与 q 所在的队伍进行比赛（数据保证此时 p 和 q 不在同一支队伍），设 p 所在的队伍有 \(siz_p\) 个人，q 所在的队伍有 \(siz_q\) 个人，则此次比赛中 p 所在队伍获胜的概率为 \(\frac{siz_p}{siz_p+siz_q}\)，q 所在队伍获胜的概率为 \(\frac{siz_q}{siz_p+siz_q}\)。获胜队伍的所有成员都可以获得一分，并且此次比赛结束后会将这两支队伍合并为一支队伍。对于这 n 个人，求出每个人的得分期望。
大致思路
如果我们暴力地计算答案，也就是每次比赛都给两队中的人一个一个地去加上本次得分的期望，那么时间复杂度会达到 \(O(n^2)\)，无法通过此题，考虑优化。我们考虑为什么这个暴力算法会很慢，也就是考虑它有哪些计算是可以省去或者暂时省去（最后再统一计算）的。那么我们假设有一场队伍 i 和队伍 j 的比赛 p，比赛结束后合并为队伍 k，那么其实队伍 k 之后的所有得分期望对于 i 和 j 中的成员都是有效的，所以我们其实可以利用一种类似前缀的东西，我们把队伍 k 产生之后的所有得分期望统计起来，最后再分别加上 i 和 j 两支队伍再比赛 p 中的得分期望就可以统计出答案。这样就可以不需要把队伍 k 产生之后的每次比赛的得分期望都去给 i 和 j 中的成员一个一个地加上。
代码实现
我们把每一次两支队伍之间的比赛视作两个个体之间的二元关系，再结合上文所说的类似前缀的东西，可以发现树可以很完美地体现出这两个性质：将二元关系转化为树边，将类似前缀的东西转化为树上的父亲和儿子之间的递进关系。
我们再考虑如何合并两支队伍，合并时我们将两支队伍视作两棵树，用一个新的节点作为新的根把这两棵树合并起来，比如我们要合并队伍 i 和队伍 j，就建立一个新的节点 k，然后从 k 连两条边分别指向 i 和 j，并且权值分别为此次比赛中队伍 i 和队伍 j 的得分期望。
然后因为题目中说每次会给出两个选手的编号，所以我们还需要每次快速判断选手所在的队伍，这个可以用并查集 \(O(n)\) 实现。
最后统计答案的时候 dfs一遍记录边权的前缀就可以完成了。
时间复杂度为 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
const int N=400200,mod=998244353;
int n,p[N],q[N],idx;
int ans[N],fa[N],siz[N];
int idx_e,head[N],inv[N];
inline int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
struct edge{
int u,v,w,nxt;
}e[N];
il void adde(int u,int v,int w){
e[++idx_e]={u,v,w,head[u]};
head[u]=idx_e;
}
il void init(){
inv[1]=1;
for(re int i=2;i<=n;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;//预处理逆元
for(re int i=1;i<=n;i++)fa[i]=i,siz[i]=1;//并查集初始化
for(re int i=n+1;i<=(n<<1);i++)fa[i]=i;
//注意这里我们额外建立的节点是没有人的
}
il int fnd(int x){
if(fa[x]==x)return x;
return fa[x]=fnd(fa[x]);
}
il void merge(int x,int y){
x=fnd(x),y=fnd(y);//找到所在队伍
idx++;//建立新的节点
fa[x]=idx,fa[y]=idx;
siz[idx]=siz[x]+siz[y];
int kop=inv[siz[idx]];
adde(idx,x,siz[x]*kop%mod),adde(idx,y,siz[y]*kop%mod);
//计算期望并建边
}
il void dfs(int x,int sum){
if(x<=n)ans[x]=sum;
//如果 <=n 说明是选手而非我们额外建立的节点，那么就记录答案
for(re int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
sum=(sum+e[i].w)%mod;//记录前缀 sum
dfs(v,sum);
sum=(sum+mod-e[i].w)%mod;
}
}
signed main(){
n=read();
init();
idx=n;
//为了避免和之前的节点编号重复，我们把新的节点从 n+1 开始编号
for(re int i=1;i<n;i++){
int p=read(),q=read();
merge(p,q);//进行比赛
}
dfs(idx,0);
for(re int i=1;i<=n;i++)cout<<ans[i]<<' ';
return 0;
}