题目大意
给定一棵树，(1) 号点为根，每个点有点权，从某一点出发每次等概率地到达相邻的点中的一个，到叶子节点位置（保证根节点度数不为(1)）位置
支持修改点权，求从根出发形成的路径的点权和期望。
题解
设 (F_x) 表示从 (x) 出发的答案，(V_x) 为 (x) 点权，(D_x) 为 (x) 的度数那么显然
[F_x=V_x+sum frac{F_{to}}{D_X} (D_x>1)\
F_x=V_x (D_x=1)
]
由于转移带环，似乎只能消元，所以你可以暴力 (O(n^3Q)) 获得 (20) 分的好成绩
仔细观察消元的过程，你会发现你可以把 (F_x) 中的 (V_k) 系数表示出来，这样就可以 (O(n^3+nQ)) 获得 (40) 分
注意到它是一棵树，意味着 (F_x) 只会出现在相邻 点上，有一个很巧妙的方法
设 (p=x)的父节点 ，我们可以假设 (F_p) 已知。
不妨设(F_x=K_xF_p+B_x)
那么对于叶子节点，显然有(K_x=0,B_x=V_X)
然后考虑展开非叶子结点的式子。
[F_x=V_x+sum frac{F_{to}}{D_X} (D_x>1)\
D_xF_x=D_xV_x+sum F_{son}+F_p\
D_xF_x=D_xV_x+sum (K_{son}F_x+B_{son})+F_p\
(D_x-sum K_{son})F_x=sum B_{son}+D_xV_x+F_p\
K_x=frac{1}{D_x-sum K_{son}}\
B_x=frac{sum B_{son}+D_xV_x}{D_x-sum K_{son}}\
]
这样可以 (O(n)) 递推出 (B_1) 即为答案，可以 (O(nQ)) 获得 (60) 分
仔细观察式子，设 (G_x=D_x-sum K_{son}) 不难发现 (V_x) 的贡献是 (frac{D_x}{prodlimits_{kin{Anc_x}}G_k})
其中 (Anc_x) 表示 (x) 及 (x) 的祖先。
这样即可 (O(nlog n+Q)) 获得满分。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<" "
#define el <<endl
#define fgx cerr<<" --------------------------- "<<endl
#define pii pair<int,int>
#define mp make_pair
#define LL long long
#define M 100020
#define mod 998244353
using namespace std;
int read(){
int nm=0,fh=1; char cw=getchar();
for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
inline int mul(int x,int y){return (LL)x*(LL)y%mod;}
inline int add(int x,int y){x+=y;return (x>=mod)?(x-mod):x;}
inline int mns(int x,int y){x-=y;return (x<0)?(x+mod):x;}
inline int upd(int &x,int y){x+=y;(x>=mod)?(x-=mod):0;}
int n,m,fs[M],nt[M<<2],to[M<<2],val[M],D[M],tmp,B[M],K[M],ans;
#define link(a,b) nt[tmp]=fs[a],fs[a]=tmp,D[to[tmp++]=b]++
inline int qpow(int x,int sq){
int res=1;
for(;sq;sq>>=1,x=mul(x,x)) if(sq&1) res=mul(res,x);
return res;
}
void dfs1(int x,int p){
if(D[x]==1){B[x]=val[x],K[x]=0;return;}
for(int i=fs[x],v;i!=-1;i=nt[i]) if((v=to[i])^p)
dfs1(v,x),upd(K[x],K[v]),upd(B[x],B[v]);
int dw=qpow(mns(D[x],K[x]),mod-2); K[x]=dw;
B[x]=mul(add(mul(D[x],val[x]),B[x]),dw);
}
void dfs2(int x,int p){
if(D[x]==1) K[x]=1; K[x]=mul(K[x],K[p]);
for(int i=fs[x];i!=-1;i=nt[i]) if(to[i]^p) dfs2(to[i],x); K[x]=mul(K[x],D[x]);
}
int main(){
n=read(),memset(fs,-1,sizeof(fs));
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
dfs1(1,0),ans=B[K[0]=1],dfs2(1,0),printf("%d
",ans);
for(int Cas=read(),dt,ps,k;Cas;--Cas){
ps=read(),dt=mns(k=read(),val[ps]),val[ps]=k;
upd(ans,mul(K[ps],dt)),printf("%d
",ans);
} return 0;
}