Description：

一棵 $n$ 个点的树，给每条边染色。颜色一共有 $c$ 种。定义 $f(i)$ 为只保留颜色为 $i$ 的边后点数大于 $1$ 的联通块个数。一个染色方案的价值为 $\begin{align}(\sum^c_{i=1}f(i))^k\end{align}$ 。求所有不同的染色方案的价值和。 答案对 $998244353$ 取模。

$1\leqslant n\leqslant 10^5,1\leqslant c\leqslant 10^9,1\leqslant k\leqslant 10^9$

Solution：

首先转化题意： $$ \begin{align} &\sum_{染色}(\sum_{i=1}^cf(i))^k\\ =&\sum_{染色}(\sum_{i=1}^c(只保留颜色c的边后的点数-边数-孤点数))^k\\ =&\sum_{染色}(c\times n-(n-1)-\sum_{i=1}^c只保留颜色c的边后的孤点数)^k\\ =&\sum_{染色}(c\times n-(n-1)-\sum_{i=1}^n点i被孤立次数)^k\\ =&\sum_{染色}(c\times n-(n-1)-\sum_{i=1}^n(c-点i周围颜色次数))^k\\ =&\sum_{染色}(1-n+\sum_{i=1}^n点i周围颜色次数)^k\\ =&\sum_{t=n-1}^{2\times n}\sum_{染色}[\sum_{i=1}^n点i周围颜色次数=t](1-n+t)^k \end{align} $$ 也就是说我们要统计所有点周围颜色个数和为某个值的方案数，之所以我们要把它转化成这样，是因为这样的话每个点对答案的贡献互相独立，这个理解的话就是把他变成一棵有根树，那么无论这个点周围的边颜色是什么，我们都可以通过它和父亲的边来调整，即把颜色轮换一下，因为所有颜色本质相同，也就是每个点在计算的时候少乘一个 $c$ ，在最后还要再乘一个 $c$ ，因为根节点不用调整，而且这也说明这个做法在图上行不通。然后我们转化的结果是可以设 $G_k$ 表示 $k$ 这个点周围有 $i$ 个颜色的方案数的生成函数，那么显然这是一个 $deg[k]$ 次多项式， $G_k(i)=S_2(deg[k],i)\times P^c_i/c$ ，而： $$ \sum{染色}[\sum{i=1}^n点i周围颜色次数=t] $$ 显然等于： $$ \prod_{k=1}^nG_k $$ 第二类斯特林数可以 $NTT$ 预处理，复杂度为 $O(\sum deg[i]\log deg[i])=O(n\log n)$ ，然后上面那个累乘式可以分治 $+NTT$ 求，注意分治的时候要按 $\sum deg$ 平均分成两半而不是直接均分，然后就做完了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,c,k;

#define P 998244353

#define MAXN 1600010

int deg[MAXN];

#define I inline

#define R register

I int Add(int a,int b){return (a + b >= P ? a + b - P : a + b);}

I int Sub(int a,int b){return (a - b < 0 ? a - b + P : a - b);}

I int Mul(int a,int b){return 1ll * a * b % P;}

I int power(int a,int b)

{

	R int res = 1;

	while(b > 0)

	{

		if(b & 1)res = Mul(res,a);

		a = Mul(a,a);

		b = b >> 1;

	}

	return res;

}

namespace poly

{

	int ww[MAXN << 1],*g = ww + MAXN;

	int rev[MAXN];

	I int init(int deg)

	{

		R int l = 0,len = 1;

		for(;len <= deg;len = len << 1)++l;

		for(R int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

		g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

		for(R int i = 2;i < len;++i)g[i] = g[i - len] = Mul(g[i - 1],g[1]);

		return len;

	}

	I void NTT(int f[],int l,int type)

	{

		for(R int i = 0;i < l;++i)

		{

			if(i < rev[i])swap(f[i],f[rev[i]]);

		}

		for(R int i = 2;i <= l;i = i << 1)

		{

			R int wn = g[type * l / i];

			for(R int j = 0;j < l;j += i)

			{

				R int w = 1;

				for(R int k = j;k < j + i / 2;++k)

				{

					R int u = f[k],t = Mul(w,f[k + i / 2]);

					f[k] = Add(u,t);

					f[k + i / 2] = Sub(u,t);

					w = Mul(w,wn);

				}

			}

		}

		if(type == -1)

		{

			R int ni = power(l,P - 2);

			for(int i = 0;i < l;++i)f[i] = Mul(f[i],ni);

		}

		return;

	}

}

#define MAXC 1000010

int fac[MAXC],inv[MAXC];

I void init()

{

	fac[0] = 1;

	for(R int i = 1;i <= c;++i)fac[i] = Mul(fac[i - 1],i);

	inv[c] = power(fac[c],P - 2);

	for(R int i = c - 1;i >= 0;--i)inv[i] = Mul(inv[i + 1],i + 1);

	return;

}

namespace ST

{

	int a[MAXN],b[MAXN];

	vector<int> S[MAXN];

	I void init_S(int k,int n)

	{

		for(R int i = 0;i <= n;++i)

		{

			a[i] = Mul(inv[i],(i & 1) ? P - 1 : 1);

			b[i] = Mul(inv[i],power(i,n));

		}

		R int len = poly::init(n * 2);

		poly::NTT(a,len,1);poly::NTT(b,len,1);

		for(R int i = 0;i < len;++i)a[i] = Mul(a[i],b[i]);

		poly::NTT(a,len,-1);

		for(R int i = 0;i <= min(n,c);++i)S[k].push_back(Mul(Mul(a[i],fac[c - 1]),inv[c - i]));

		for(R int i = 0;i < len;++i)a[i] = b[i] = 0;

		return;

	}

}

int v[MAXN],d[MAXN];

int s[21][MAXN];

void solve(int d,int l,int r)

{

	if(l == r)

	{

		for(R int i = 0;i < ST::S[l].size();++i)s[d][i] = ST::S[l][i];

		return;

	}

	R int sum = 0;

	for(R int i = l;i <= r;++i)sum += ST::S[i].size();

	R int pos = l,cur = ST::S[l].size();

	while(cur + ST::S[pos + 1].size() <= sum / 2){++pos;cur += ST::S[pos].size();}

	solve(d + 1,l,pos);

	for(R int i = 0;i <= sum;++i)s[d][i] = s[d + 1][i];

	for(R int i = 0;i <= sum;++i)s[d + 1][i] = 0;

	solve(d + 1,pos + 1,r);

	R int len = poly::init(sum);

	poly::NTT(s[d],len,1);poly::NTT(s[d + 1],len,1);

	for(R int i = 0;i < len;++i)s[d][i] = Mul(s[d][i],s[d + 1][i]);

	poly::NTT(s[d],len,-1);

	for(R int i = 0;i < len;++i)s[d + 1][i] = 0;//cout << l << " " << r << endl;

	return;

}

int main()

{

	freopen("ranse.in","r",stdin);

	freopen("ranse.out","w",stdout);

	scanf("%d%d%d",&n,&c,&k);

	if(k == 0)

	{

		cout << power(c,n - 1) << endl;

		return 0;

	}

	R int a,b;

	for(R int i = 1;i < n;++i)

	{

		a = rd();b = rd();

		++deg[a];++deg[b];

	}

	init();

	for(R int i = 1;i <= n;++i)ST::init_S(i,deg[i]);

	solve(0,1,n);

	int ans = 0;

	for(R int i = n;i <= 2 * n;++i)ans = Add(ans,Mul(s[0][i],power(1 - n + i,k)));

	cout << Mul(ans,c) << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}