题目概述
解题报告
这题竟是脑子题……
显然这是个树上解方程的题目，设 $D_x$ 为 $x$ 的度数，$fa$ 为 $x$ 的父亲，$u$ 为 $x$ 儿子：
$$ f_{x}={1\over D_x}(f_{fa}+\sum_{u}f_u)+1 $$
类似随机游走，我们不难发现可设 $f_x=a_xf_{fa}+b_x$ ，则：
$$ (D_x-\sum_ua_u)f_x=f_{fa}+\sum_u b_u+D_x $$
由于 $a_u$ 出现在分母里，所以很不可维护，但是如果我们从叶子节点开始考虑，显然 $f_x=f_{fa}+1$ ，此时 $a_x=1$ ，考虑叶子节点的父亲 $fa$ ，则：
$$ (D_{fa}-\sum_{u}a_u)f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa}\\ (D_{fa}-\sum_{u}1)f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa}\\ f_{fa}=f_{fafa}+\sum_{u}b_u+D_{fa} $$
以此类推不难发现 $a_x$ 均为 $1$ ，我们只需要假设 $f_x=f_{fa}+b_x$ ，然后稍作分析，会发现 $b_x$ 其实就等于 $x$ 子树中所有节点度数的和，记为 $sum_x$ ，则 $f_{x}=f_{fa}+sum_x$ 。由于 $f_1=0$ ，也就是说 $f_x$ 其实就是 $x$ 到 $1$ 路径上所有 $sum$ 的和。
这样问题就变得容易分析了。当一条边 $x\to fa$ 改为单向边时，说明 $fa$ 往上不再统计 $x$ 子树里的度数，而 $x$ 子树中的不受影响。那么 $f_S$ 减少的值可以这么考虑：求出 $fa$ 和 $S$ 的 $LCA$ ，首先 $fa\to LCA$ 上不可以再选边，否则 $x\to fa$ 将影响不到 $S$ 。然后考虑 $LCA$ 往上走多少点遇到了另一条单向边，若点数为 $i$ 则 $f_S$ 减少的值为 $i\cdot (sum_{x}+1)$ 。特别的，$1$ 号点即使能走到也没有贡献。
枚举边 $x\to fa$ ，假设除掉 $x\to LCA$ 的边后剩下 $m$ 条边，$LCA$ 到 $1$ 路径上边的个数为 $d$ 。由于这条边改为单向的贡献恒为 $sum_x+1$ ，我们只需要考虑所有情况下 $i$ 的和。分为两种：$LCA$ 到 $1$ 路径上选了边（此时考虑最近的边），以及 $LCA$ 到 $1$ 路径上没有选边。第一种：$\sum_{i=1}^{d}i{m-i\choose K-2}$ ，第二种：$d{m-d\choose K-1}$ 。
如果我们直接枚举第一种情况复杂度肯定是不能接受的，因此我们考虑利用组合数公式简化式子：
$$ \sum_{i=0}^{n}{i\choose k}={n+1\choose k+1}\\ \begin{aligned} \sum_{i=1}^{d}i{m-i\choose K-2}&=\sum_{i=1}^{d}\sum_{j=i}^{d}{m-j\choose K-2}=\sum_{i=1}^{d}\sum_{j=m-d}^{m-i}{j\choose K-2}\\ &=\sum_{i=1}^{d}(\sum_{j=0}^{m-i}{j\choose K-2}-\sum_{j=0}^{m-d-1}{j\choose K-2})\\ &=\sum_{i=1}^{d}({m-i+1\choose K-1}-{m-d\choose K-1})\\ &=\sum_{i=m-d+1}^{m}{i\choose K-1}-d{m-d\choose K-1}\\ &=\sum_{i=0}^{m}{i\choose K-1}-\sum_{i=0}^{m-d}{i\choose K-1}-d{m-d\choose K-1}\\ &={m+1\choose K}-{m-d+1\choose K}-d{m-d\choose K-1} \end{aligned} $$
这样就可以快速计算了，令 $val={m+1\choose K}-{m-d+1\choose K}$ ，需要减去的值就是 $val(sum_x+1)$ 。
示例程序
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000000,maxe=maxn<<1,LOG=20,MOD=998244353;
int n,K,S,D[maxn+5],sum[maxn+5],f[maxn+5];
int E,lnk[maxn+5],nxt[maxe+5],to[maxe+5];
int dep[maxn+5],ST[maxn+5][LOG+1];
int fac[maxn+5],INV[maxn+5],ans;
#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
dep[x]=dep[pre]+1;ST[x][0]=pre;sum[x]=D[x];
for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
for (int j=lnk[x];j;j=nxt[j])
if (to[j]!=pre) DFS(to[j],x),sum[x]+=sum[to[j]];
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
void DP(int x,int pre=0){
for (int j=lnk[x];j;j=nxt[j])
if (to[j]!=pre) f[to[j]]=ADD(f[x],sum[to[j]]),DP(to[j],x);
}
void Make(int n){
INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
inline int C(int x,int y) {return x<y?0:MUL(fac[x],MUL(INV[y],INV[x-y]));}
int LCA(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int j=LOG;~j && dep[x]>dep[y];j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
if (x==y) return x;
for (int j=LOG;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];
return ST[x][0];
}
int main(){
readi(n);readi(K);readi(S);
for (int i=1,x,y;i<n;i++)
readi(x),readi(y),Add(x,y),Add(y,x),D[x]++,D[y]++;
DFS(1);DP(1);Make(n);
if (!K) {printf("%d\n",f[S]);return 0;}
ans=MUL(f[S],C(n-1,K));
for (int i=2;i<=n;i++){
int lca=LCA(S,ST[i][0]),m=n-1-(dep[i]-dep[lca]),d=dep[lca]-1;
int val=ADD(C(m+1,K),MOD-C(m-d+1,K));
ans=ADD(ans,MOD-MUL(val,sum[i]+1));
}
ans=MUL(ans,MUL(MUL(fac[K],fac[n-1-K]),INV[n-1]));
printf("%d\n",ans);
return 0;
}
