Description
Solution
套路题...
全他娘的是套路...
首先如何处理仙人掌，可以在线拿 \(lct\) 维护，或者离线之后树剖。（\(lct\) 维护太毒了写不来，就离线树剖了又好写又不用调
离线树剖的意思就是按加边时间为权值建出一棵最小生成树（或者生成森林），这就是最终的仙人掌的一棵生成树了。
加边的时候如果这是条树边那就直接加上，如果不是树边，那就在线段树上查一下这个环是否有边被覆盖，只要有一条边被覆盖那就不满足仙人掌性质，那就不能加这条边进去，否则加进去然后线段树区间赋值就好了。
然后怎么求期望联通块数？
如果这是个森林的话，期望联通块数=期望点数-期望边数
那要是个沙漠呢？
考虑一下森林的这个式子是怎么来的，就是最开始有点数个联通块，然后每加一条边就合并两个联通块，所以是点数-边数。
那放到仙人掌上，发现每条形成环的非树边都被多减了一次，那再加回来就好了。而成环的非树边就恰好等于仙人掌的环数，因为一条边最多只会出现在一个环里。所以沙漠的期望联通块数=期望点数-期望边数+期望环数。
然后分开考虑就好了，因为点还有颜色，那我们规定一条边是白的当且仅当两端点都是白色，一个环是白的当且仅当环上的所有点都是白色。黑色同理。
先算点数。根据期望的线性性，一个点是白色点的概率就是 \((\frac{n-1}n)^t\)，那对期望的贡献就是 \(1\cdot (\frac{n-1}n)^t\) ，黑色点拿 \(1\) 减一下就行了。
再算边数。一条边是白色边的概率是 \((\frac{n-2}n)^t\) ，是黑色边的概率容斥一下，就是 \(2\cdot(1-(\frac{n-1}n)^t)-(1-(\frac{n-2}n)^t)=1+(\frac{n-2}n)^t-2\cdot (\frac{n-1}n)^t\) ，含义画一个Venn图就很清楚了。
然后是环数，白色环的概率很好算，就是 \((\frac{n-len}n)^t\)，其中 \(len\) 是环长。那黑色环呢，也是容斥一下，枚举至少有 \(j\) 个白点，所以 \(f(len)=\sum\limits_{j=0}^{len} (-1)^j \cdot C_{len}^j\cdot (\frac{n-j}n)^t\) 。
嗯然后就做完了。
Code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using std::swap;
typedef long long ll;
#define int long long
const int N=3e5+5;
const int mod=998244353;
int n,m,t,w;
int fac[N],ifac[N];
int cnt,head[N],is[N];
int father[N],ques[N][2];
struct Edge{
int to,nxt;
}edge[N<<1];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
namespace slpf{
#define ls x<<1
#define rs x<<1|1
#define lss ls,l,mid,ql,qr
#define rss rs,mid+1,r,ql,qr
int sze[N],son[N],fa[N];
int flag[N<<2],sum[N<<2];
int tot,dfn[N],top[N],d[N];
void dfs(int now){
sze[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(sze[to]) continue;
fa[to]=now;d[to]=d[now]+1;
dfs(to);sze[now]+=sze[to];
son[now]=sze[to]>sze[son[now]]?to:son[now];
}
}
void dfs2(int now,int low){
dfn[now]=++tot;top[now]=low;
if(son[now]) dfs2(son[now],low);
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(dfn[to]) continue;
dfs2(to,to);
}
}
void pushup(int x){
sum[x]=sum[ls]|sum[rs];
}
void pushdown(int x){
if(!flag[x]) return;
flag[ls]=flag[rs]=sum[ls]=sum[rs]=1;
flag[x]=0;
}
void modify(int x,int l,int r,int ql,int qr){
if(ql<=l and r<=qr) return flag[x]=sum[x]=1,void();
pushdown(x);int mid=l+r>>1;
if(ql<=mid) modify(lss);
if(mid<qr) modify(rss);
pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
if(ql<=l and r<=qr) return sum[x];
pushdown(x);int mid=l+r>>1,ans=0;
if(ql<=mid) ans|=query(lss);
if(mid<qr) ans|=query(rss);
return ans;
}
int ask(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans|=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
} if(d[x]<d[y]) swap(x,y);
if(x!=y) ans|=query(1,1,n,dfn[y]+1,dfn[x]);
return ans;
}
int change(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
modify(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
} if(d[x]<d[y]) swap(x,y);
if(x!=y) modify(1,1,n,dfn[y]+1,dfn[x]);
return y;
}
}
int ksm(int a,int b=mod-2,int ans=1){
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod; b>>=1;
} return ans;
}
int getint(){
int X=0,w=0;char ch=getchar();
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
int find(int x){
return father[x]==x?x:father[x]=find(father[x]);
}
int dec(int x,const int &y){
return x-y<0?x-y+mod:x-y;
}
int C(int n,int m){
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main(){
freopen("cactus.in","r",stdin);freopen("cactus.out","w",stdout);
gi(n),gi(m),gi(t),gi(w);
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n]);
for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++) father[i]=i;
int invn=ksm(ksm(n),t),baid=ksm(n-1,t)*invn%mod,baib=ksm(n-2,t)*invn%mod,heib=(baib-baid*2%mod+1+mod)%mod;
for(int i=1;i<=m;i++){
gi(ques[i][0]),gi(ques[i][1]);
int r1=find(ques[i][0]),r2=find(ques[i][1]);
if(r1!=r2) father[r1]=r2,is[i]=1,add(ques[i][0],ques[i][1]),add(ques[i][1],ques[i][0]);
} for(int i=1;i<=n;i++) if(!slpf::dfn[i]) slpf::d[i]=1,slpf::dfs(i),slpf::dfs2(i,i);
int ans=(w==1?n:baid*n%mod);
for(int i=1;i<=m;i++){
if(is[i]){
ans=dec(ans,baib);
if(w==1) ans=dec(ans,heib);
} else{
if(!slpf::ask(ques[i][0],ques[i][1])){
int z=slpf::change(ques[i][0],ques[i][1]);
ans=dec(ans,baib);
if(w==1) ans=dec(ans,heib);
int len=slpf::d[ques[i][0]]+slpf::d[ques[i][1]]-slpf::d[z]*2+1;
(ans+=ksm(n-len,t)*invn%mod)%=mod;
if(w==1){
int res=0;
for(int j=0;j<=len;j++)
(res+=(j&1?mod-C(len,j):C(len,j))*ksm(n-j,t)%mod*invn%mod)%=mod;
(ans+=res)%=mod;
}
}
} print(ans),putc('\n');
} return io::flush(),0;
}