真的很想吐。
题目的意思大概就是在一棵树上选出\(k\)个联通块，使得这\(k\)个联通块有交。
显然联通块的交还是联通块，因此转化为对联通块计数。而联通块个数等于点数减去边数，因此可以分别对点和边计数。
设\(f_{i,j}\)表示\(i\)子树中最深的点小于\(j\)的联通块有多少个，\(g_{i,j}\)表示\(i\)子树外最深为\(j\)的联通块有多少个。则点的答案为\(f_{i,L}\times g_{i,L}\)，边的答案为\(f_{i,L-1}\times (g_{i,L}-1)\)。
转移方程大概就是\(f_{i,j}=\prod\limits_{(u,i)\in E,u\not=fa_i}{f_{u,j}+1}\)，\(g\)类似。
发现第二维和深度有关，考虑长链剖分。长链剖分优化\(f\)是套路的，即我们要支持单点查/改，整体加，后缀乘。可以全局维护加法和乘法标记，然后后缀乘转化为前缀乘，复杂度是正确的。
优化\(g\)的过程可以看作\(f\)的反过程。容易发现对于\(i\)子树内从父亲拿下来的信息，只有深度在\([L-len_i,L]\)范围内的状态是有用的，因此轻儿子暴力转移的复杂度和长剖类似，是\(O(n)\)的，也要维护像\(f\)类似的东西。
重儿子直接从轻儿子转移复杂度也是正确的。
总共的复杂度是\(O(n\log p)\)，瓶颈在逆元上。但是有个问题，如果恰好模\(p\)余\(0\)是没有逆元的。但是这样的概率可以看作在\([0,p-1]\)中选一个数选到\(p-1\)的概率，则直接暴力即可。
然后exgcd的逆元显著快于费马小定理，卡卡常能过。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e6+5,M=2.5e3+5,K=1e5+5,mod=998244353,Mod=mod-1;const int INF=2e9+7;const db eps=1e-5;mt19937 rnd(263082);
int n,m,k,x,y,z,Sn[N],Le[N],B[N],Bh;ll Ans;vector<int> S[N];
ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
void EG(ll x,int p,ll &a,ll &b){if(!p){a=1;b=0;return;}EG(p,x%p,a,b);swap(a,b);b-=x/p*a;}
ll GI(ll x){ll y,z;EG(x,mod,y,z);return (y%mod+mod)%mod;}
void Make1(int x,int La){for(int i:S[x]) i^La&&(Make1(i,x),Le[i]+1>Le[x]&&(Le[x]=Le[i]+1,Sn[x]=i));}
void Make2(int x,int La){if(!Sn[x]) return;B[Sn[x]]=B[x]+1;Make2(Sn[x],x);for(int i:S[x]) i^La&&i^Sn[x]&&(B[i]=Bh+1,Bh+=Le[i]+1,Make2(i,x),0);}
struct Node{
ll k,b,inv;
Node operator *(const Node &B)const{return (Node){k*B.k%mod,b*B.k%mod,inv*B.inv%mod};}
Node operator +(const Node &B)const{return (Node){k,(b+B.b)%mod,inv};}
ll calc(ll x){return (x*k+b)%mod;}
}F[N],Cl=(Node){1,0,1},G[N];
ll f[N],g[N];
vector<pair<int,ll>> SS[N];
void mul(ll &x,ll w,Node p){x=(p.calc(x)*w%mod+mod-p.b)*p.inv%mod;}
void dfs1(int x,int La){
int i,j;
if(Sn[x])dfs1(Sn[x],x),F[B[x]]=F[B[x]+1];else F[B[x]]=Cl;
f[B[x]]=(mod-F[B[x]].b)*F[B[x]].inv%mod;F[B[x]]=F[B[x]]+(Node){0,1,0};
for(int i:S[x]) if(i^La&&i^Sn[x]){
dfs1(i,x);for(j=0;j<Le[i];j++) SS[x].PB({B[x]+j+1,f[B[x]+j+1]}),mul(f[B[x]+j+1],F[B[i]].calc(f[B[i]+j])+1,F[B[x]]);
ll s=(F[B[i]].calc(f[B[i]+Le[i]])+1)%mod,p=GI(s);
// if(!s){
// for(j=Le[i]+1;j<=Le[x];j++) SS[x].PB({B[x]+j,f[B[x]+j]}),mul(f[B[x]+j],0,F[B[x]]);
// }else{
for(j=0;j<=Le[i];j++) mul(f[B[x]+j],p,F[B[x]]);
F[B[x]]=F[B[x]]*(Node){s,0,p};
// }
}
}
void dfs2(int x,int La){
int i,j;if(Le[x]>=m) g[B[x]+m]=(mod-G[B[x]].b)*G[B[x]].inv%mod;G[B[x]].b++;
if(Sn[x]){
for(int i:S[x]) if(i^La&&i^Sn[x]){
//if(x==9&&i==8) cerr<<"asdf "<<G[B[x]].calc(g[B[x]+1])<<' '<<F[B[x]].calc(f[B[x]+min(Le[x],m-1)])<<' '<<mpow(F[B[i]].calc(f[B[i]+min(Le[i],m-2)])+1)<<'\n';
for(j=0;j<=Le[i];j++) if(m-j-1>0){
ll s=(F[B[i]].calc(f[B[i]+min(Le[i],m-j-2)])+1)%mod;
if(s) g[B[i]+j]=G[B[x]].calc(g[B[x]+j+1])*F[B[x]].calc(f[B[x]+min(Le[x],m-j-1)])%mod*GI(s)%mod;
}
else if(m-j-1==0) g[B[i]+j]=G[B[x]].calc(g[B[x]+j+1])*F[B[x]].calc(f[B[x]+min(Le[x],m-j-1)])%mod;
else if(m-j-1<0) g[B[i]+j]=0;
}
G[B[x]+1]=G[B[x]]+G[B[x]+1];
for(int i:S[x]) if(i^La&&i^Sn[x]){
for(j=0;j<=Le[i];j++) if(j+2>=m-Le[Sn[x]]&&j+2<=m) mul(g[B[x]+1+m-(j+2)],F[B[i]].calc(f[B[i]+j])+1,G[B[x]+1]);
if(Le[i]+2<m){
ll s=(F[B[i]].calc(f[B[i]+Le[i]])+1)%mod,p=GI(s);
//if(!s){
// for(j=Le[i]+1;j<=m-2;j++) if(j+2>=m-Le[Sn[x]]) mul(g[B[x]+1+m-(j+2)],0,G[B[x]+1]);
//} else{
for(j=-2;j<=Le[i];j++) if(j+2>=m-Le[Sn[x]]&&j+2<=m) mul(g[B[x]+1+m-(j+2)],p,G[B[x]+1]);
G[B[x]+1]=G[B[x]+1]*(Node){s,0,p};
//}
}
}
/*for(int i:S[x]) if(i^La){
for(j=1;j<=m;j++) g[i][j]=g[x][j-1];
for(j=2;j<=m;j++) g[i][j]=g[i][j]*F[B[x]].calc(f[B[x]+min(Le[x],j-1)])%mod*mpow(F[B[i]].calc(f[B[i]+min(Le[i],j-2)])+1)%mod;
}*/
}
reverse(S[x].begin(),S[x].end());
if(La&&m)Ans-=mpow(F[B[x]].calc(f[B[x]+min(m-1,Le[x])])*(G[B[x]].calc(g[B[x]])-1+mod)%mod,k);Ans+=mpow(F[B[x]].calc(f[B[x]+min(m,Le[x])])*G[B[x]].calc(g[B[x]])%mod,k);
printf("%d %lld %lld\n",x,F[B[x]].calc(f[B[x]+min(m,Le[x])]),G[B[x]].calc(g[B[x]]));
reverse(SS[x].begin(),SS[x].end());for(auto i:SS[x]) f[i.first]=i.second;
if(Sn[x]){
for(int i:S[x]) if(i^La&&i^Sn[x]){
//if(x==9&&i==8) cerr<<"asdf "<<G[B[x]].calc(g[B[x]+1])<<' '<<F[B[x]].calc(f[B[x]+min(Le[x],m-1)])<<' '<<mpow(F[B[i]].calc(f[B[i]+min(Le[i],m-2)])+1)<<'\n';
for(j=0;j<=Le[i];j++) if(m-j-1>0){
ll s=(F[B[i]].calc(f[B[i]+min(Le[i],m-j-2)])+1)%mod;
if(!s){
g[B[i]+j]=G[B[x]].calc(g[B[x]+j+1]);
for(int p:S[x]) if(i^p&&p^La) g[B[i]+j]=g[B[i]+j]*(F[B[p]].calc(f[B[p]+min(m-j-2,Le[p])])+1)%mod;
}
}
}
}
for(int i:S[x]) i^La&&(i^Sn[x]&&(G[B[i]]=Cl,0),dfs2(i,x),0);
}
int main(){
freopen("hope.in","r",stdin);freopen("hope.out","w",stdout);
int i,j;scanf("%d%d%d",&n,&m,&k);for(i=1;i<n;i++) scanf("%d%d",&x,&y),S[x].PB(y),S[y].PB(x);
Make1(1,0);B[1]=1;Bh=Le[1]+1;Make2(1,0);
dfs1(1,0);
G[1]=Cl;dfs2(1,0);
printf("%lld\n",(Ans%mod+mod)%mod);
}