我知道没有人会来帮我调这种题，但我还是要发帖求助。

wa on 7,9。

调了一周了，目前是最好结果。

从 LOJ 上下了数据 #7 玩了一会，得出的结果是：仅在 466 和 10185 两个节点上的 $g$ 值不对。这两个点都是叶子，有同样的父亲，深度均为 22。实在调不出来了。

如果真的有人愿意为这题和我的这份代码驻足，那代码中的调试痕迹说不定（？）能给予你帮助。

我们所可以自慰的，想来想去，也还是所谓对于将来的希望。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e6+5,MOD=998244353;
char buf[1<<20];
int ppp,qqq;
inline char gc()
{
    if(ppp==qqq) ppp=0,qqq=fread(buf,1,1<<20,stdin);
    return buf[ppp++];
}
#define gc() getchar()
inline int rd()
{
    char x;
    while((x=gc())<'0'||x>'9');int t=x-'0';
    while((x=gc())>='0'&&x<='9') t=t*10+x-'0';
    return t;
}
inline int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1) ret=1ll*ret*x%MOD;
        x=1ll*x*x%MOD;
        y>>=1;
    }
    return ret;
}
// gg 调试用，gg[i]=g[i][L]
// ansf[i][0] 存 f[i][L]-1，ansf[i][1] 存 f[i][L-1]-1
int bg[N],nx[N*2],to[N*2],gg[N],tl,n,L,k,ansf[N][2],alans;
inline void addedge(int x,int y)
{
    nx[++tl]=bg[x];
    bg[x]=tl;
    to[tl]=y;
}
int fa[N],dep[N],mxd[N],dfn[N],son[N],dfc;
struct edge
{
    int bel,x;
    edge(int bel=0,int x=0): bel(bel),x(x) {}
};
vector<edge> e[N];
vector<int> s[N];

// 长链剖分预处理
void dfs1(int now,int f,int depth)
{
    fa[now]=f,dep[now]=mxd[now]=depth;
    for(int i=bg[now];i;i=nx[i])
    {
        int aim=to[i];
        if(aim==f) continue;
        dfs1(aim,now,depth+1);
        if(mxd[aim]>mxd[now]) mxd[now]=mxd[aim],son[now]=aim;
    }
}
void dfs2(int now)
{
    dfn[now]=++dfc;
    if(son[now]) dfs2(son[now]);
    for(int i=bg[now];i;i=nx[i])
    {
        int aim=to[i];
        if(aim==fa[now]||aim==son[now]) continue;
        dfs2(aim);
        e[mxd[aim]-dep[now]].push_back(edge(now,aim));
    }
    if(son[now]) e[mxd[son[now]]-dep[now]].push_back(edge(now,son[now]));
}

//一般 dp 值及其逆元预处理
int pref[N],ppf[N],finv[N];
void dfs_predp(int now)
{
    pref[now]=1;
    for(int i=bg[now];i;i=nx[i])
    {
        int aim=to[i];
        if(aim==fa[now]) continue;
        dfs_predp(aim);
        pref[now]=1ll*pref[now]*pref[aim]%MOD;
    }
    pref[now]=(pref[now]+1)%MOD;
}
void get_inv()
{
    ppf[0]=1;
    for(int i=1;i<=n;i++)
    {
        ppf[i]=ppf[i-1]; 
        if(pref[i]) ppf[i]=1ll*ppf[i]*pref[i]%MOD;
    }
    int alinv=qpow(ppf[n],MOD-2),suf=1;
    for(int i=n;i>=1;i--)
    {
        if(pref[i])
        {
            finv[i]=1ll*ppf[i-1]*suf%MOD*alinv%MOD;
            suf=1ll*suf*pref[i]%MOD;
        }
    }
}

//回退数据结构
vector<vector<int> > rb[N];
vector<int> tprd;
//add：全局加，mul：全局乘，imul：全局乘逆元，zval：同值区数组中值，zlim：同值区起始位置
int f[N],add_f[N],mul_f[N],imul_f[N],zval_f[N],zlim_f[N];
void get_f(int now)
{
    int i,j,siz=s[now].size(),num=dfn[now];
    if(son[now])
    {
        int ts=son[now];
        get_f(ts);
        add_f[now]=add_f[ts];
        mul_f[now]=mul_f[ts];
        imul_f[now]=imul_f[ts];
        zval_f[now]=zval_f[ts];
        zlim_f[now]=zlim_f[ts];
    }
    else mul_f[now]=imul_f[now]=1,zlim_f[now]=1e9;
    for(i=siz-2;i>=0;i--)
    {
        tprd.clear();
        int aim=s[now][i];
        get_f(aim);
        tprd.clear();
        int num2=dfn[aim],depth=mxd[aim]-dep[aim];
        //printf("%d %d %d %d\n",now,aim,mul_f[now],add_f[now]);
        for(j=L-depth-1;j<L;j++)
        {
            if(j<0)
            {
                tprd.push_back(0);
                continue;
            }
            else if(j==0)
            {
                tprd.push_back(1);
                continue;
            }
            int tp=num+j,real;
            if(tp>=zlim_f[now]) real=(1ll*zval_f[now]*mul_f[now]+add_f[now])%MOD;
            else if(j>mxd[now]-dep[now]) real=(mul_f[now]+add_f[now])%MOD;
            else real=(1ll*f[tp]*mul_f[now]+add_f[now])%MOD;
            tprd.push_back(real);
        }
        rb[now].push_back(tprd);
        for(j=0;j<depth;j++)
        {
            int tp=num+j+1,tp2=num2+j;
            if(tp>=zlim_f[now])
            {
                f[tp]=zval_f[now];
                zlim_f[now]++;
            }
            int real=(1ll*f[tp]*mul_f[now]+add_f[now])%MOD,real2;
            if(pref[aim]) real=1ll*real*finv[aim]%MOD;
            if(tp2>=zlim_f[aim]) real2=(1ll*zval_f[aim]*mul_f[aim]+add_f[aim])%MOD;
            else real2=(1ll*f[tp2]*mul_f[aim]+add_f[aim])%MOD;
            f[tp]=1ll*(1ll*real*real2-add_f[now]+MOD)%MOD*imul_f[now]%MOD;
        }
        if(!pref[aim])
        {
            zlim_f[now]=min(zlim_f[now],num+depth+1);
            zval_f[now]=1ll*(MOD-add_f[now])*imul_f[now]%MOD;
        }
        else
        {
            mul_f[now]=1ll*mul_f[now]*pref[aim]%MOD;
            imul_f[now]=1ll*imul_f[now]*finv[aim]%MOD;
            add_f[now]=1ll*add_f[now]*pref[aim]%MOD;
        }
    }
    f[num]=1ll*(MOD+1-add_f[now])*imul_f[now]%MOD;
    add_f[now]=(add_f[now]+1)%MOD;
    int real,pos=num+min(L,mxd[now]-dep[now]);
    if(pos>=zlim_f[now]) real=(1ll*zval_f[now]*mul_f[now]+add_f[now])%MOD;
    else real=(1ll*f[pos]*mul_f[now]+add_f[now])%MOD;
    ansf[now][0]=(real-1+MOD)%MOD;
    if(L)
    {
        pos=num+min(L-1,mxd[now]-dep[now]);
        if(pos>=zlim_f[now]) real=(1ll*zval_f[now]*mul_f[now]+add_f[now])%MOD;
        else real=(1ll*f[pos]*mul_f[now]+add_f[now])%MOD;
        //printf("%d %d\n",now,real);
        ansf[now][1]=(real-1+MOD)%MOD;
    }
}
//prf：前缀 f 乘积数组
int prf[N],mul_prf[N],zlim_prf[N];
int g[N],add_g[N],mul_g[N],imul_g[N],zval_g[N],zlim_g[N];
void get_g(int now)
{
    int i,j,siz=s[now].size(),num=dfn[now],rv;
    if(num<=zlim_g[now]) rv=(1ll*zval_g[now]*mul_g[now]+add_g[now])%MOD;
    else rv=(1ll*g[num]*mul_g[now]+add_g[now])%MOD;
    gg[now]=rv;
    alans=(alans+qpow(1ll*ansf[now][0]*rv%MOD,k))%MOD;
    alans=(alans-qpow(1ll*ansf[now][1]*(rv-1+MOD)%MOD,k)+MOD)%MOD;
    mul_prf[now]=1,zlim_prf[now]=1e9;
    for(i=0;i<siz-1;i++)
    {
        int aim=s[now][i];
        int num2=dfn[aim],depth=mxd[aim]-dep[aim];
        tprd=rb[now].back();
        for(j=0;j<=depth;j++)
        {
            int tp=num+L-j-1,tp2=num2+j,tp3=num+j+1,lf,rt,tg;
            if(L-j-1<0) break;
            if(tp>=zlim_prf[now]) lf=0;
            else if(L-j-1>mxd[now]-dep[now]) lf=mul_prf[now];
            else lf=1ll*prf[tp]*mul_prf[now]%MOD;
            rt=tprd[depth-j];
            if(tp3<=zlim_g[now]) tg=(1ll*zval_g[now]*mul_g[now]+add_g[now])%MOD;
            else if(j+1>mxd[now]-dep[now]) tg=(mul_g[now]+add_g[now])%MOD;
            else tg=(1ll*g[tp3]*mul_g[now]+add_g[now])%MOD;
            //printf("tp=%d lf=%d rt=%d tg=%d\n",aim,lf,rt,tg);
            g[tp2]=(1ll*lf*rt%MOD*tg+1)%MOD;
        }
        for(j=0;j<depth;j++)
        {
            int tp=num+j+1,tp2=num2+j,real2;
            if(tp>=zlim_prf[now]) break;
            if(pref[aim]) prf[tp]=1ll*prf[tp]*finv[aim]%MOD;
            if(tp2>=zlim_f[aim]) real2=(1ll*zval_f[aim]*mul_f[aim]+add_f[aim])%MOD;
            else real2=(1ll*f[tp2]*mul_f[aim]+add_f[aim])%MOD;
            prf[tp]=1ll*prf[tp]*real2%MOD;
        }
        if(pref[aim]) mul_prf[now]=1ll*mul_prf[now]*pref[aim]%MOD;
        else zlim_prf[now]=min(zlim_prf[now],num+depth+1);
        rb[now].pop_back();
        mul_g[aim]=imul_g[aim]=1;
        get_g(aim);
    }
    if(son[now])
    {
        for(i=0;i<siz-1;i++)
        {
            int aim=s[now][i];
            int num2=dfn[aim],depth=mxd[aim]-dep[aim];
            for(j=0;j<depth;j++)
            {
                int tp=num+L-j-1,tp2=num2+j;
                if(L-j-1<=0) break;
                if(L-j-1>mxd[now]-dep[now]) continue;
                if(tp<=zlim_g[now])
                {
                    g[tp]=zval_g[now];
                    zlim_g[now]=tp-1;
                }
                int real=(1ll*g[tp]*mul_g[now]+add_g[now])%MOD,real2;
                if(pref[aim]) real=1ll*real*finv[aim]%MOD;
                if(tp2>=zlim_f[aim]) real2=(1ll*zval_f[aim]*mul_f[aim]+add_f[aim])%MOD;
                else real2=(1ll*f[tp2]*mul_f[aim]+add_f[aim])%MOD;
                g[tp]=1ll*(1ll*real*real2%MOD-add_g[now]+MOD)*imul_g[now]%MOD;
            }
            if(!pref[aim])
            {
                zlim_g[now]=max(zlim_g[now],num+L-depth-1);
                zval_g[now]=1ll*(MOD-add_g[now])*imul_g[now]%MOD;
            }
            else
            {
                mul_g[now]=1ll*mul_g[now]*pref[aim]%MOD;
                imul_g[now]=1ll*imul_g[now]*finv[aim]%MOD;
                add_g[now]=1ll*add_g[now]*pref[aim]%MOD;
                if(L<=mxd[now]-dep[now])
                {
                    int tp=num+L,real;
                    real=1ll*(1ll*g[tp]*mul_g[now]%MOD+add_g[now])*finv[aim]%MOD;
                    g[tp]=1ll*(real-add_g[now]+MOD)*imul_g[now]%MOD;
                }
            }
        }
        add_g[son[now]]=(add_g[now]+1)%MOD;
        mul_g[son[now]]=mul_g[now];
        imul_g[son[now]]=imul_g[now];
        zval_g[son[now]]=zval_g[now];
        zlim_g[son[now]]=zlim_g[now];
        if(L+1<=mxd[now]-dep[now]) g[num+L+1]=1ll*(MOD-add_g[now])*imul_g[now]%MOD;
        get_g(son[now]);
    }
}
int main()
{
//  freopen("data.in","r",stdin);
//  freopen("data.out","w",stdout);
    int i,j;
    n=rd(),L=rd(),k=rd();
    for(i=1;i<n;i++)
    {
        int x=rd(),y=rd();
        addedge(x,y),addedge(y,x);
    }
    dfs1(1,0,1);dfs2(1);
    dfs_predp(1);get_inv();
//  printf("%d %d\n",fa[466],fa[10185]);
//  for(i=1;i<=n;i++) if(!pref[i]) printf("%d\n",i);
    for(i=1;i<n;i++)
    {
        int siz=e[i].size();
        for(j=0;j<siz;j++) s[e[i][j].bel].push_back(e[i][j].x);
    }
    get_f(1);
//  for(i=1;i<=n;i++) printf("%d %d %d\n",i,ansf[i][0],ansf[i][1]);
    mul_g[1]=imul_g[1]=add_g[1]=1;
    for(i=1;i<=n;i++) prf[i]=1;
    get_g(1);
//  for(i=1;i<=n;i++) printf("%d g=%d\n",i,gg[i]);
    printf("%d",alans);
    return 0;
}
/*
10 10 9
2 4
1 8
5 8
7 8
10 9
8 2
1 10
8 3
5 6
*/