观察到分子之间的差别很小，可以提前背包算出来 \(\prod_j (x-x_j)\)，转移是枚举当前选前面的 \(x\) 还是后边的 \(-x_j\)，\(f[i]=f[i-1]-f[i]*x_j\)，分母可以预处理逆元求出来。
那现在问题就只剩下了，分子多乘了一个 \(x-x_i\)，我们要把这个退背包回去。
实际上也很简单，因为 \(f[j]=f'[j-1]-f'[j]*x_i\)，我们实际上要求的是 \(f'[j]\)，那把 \(j\) 从小到大枚举，然后移项一下就行了。
那求出来每项的系数之后，第 \(k\sim n\) 项的和就是答案了。
Code #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; typedef unsigned int ui; const int N=1670; const int M=N*200; const ui mod=64123; #define ls ch[x][0] #define rs ch[x][1] int head[N],tot,dp[M],d[N]; ui ans[N],f[N],in[N],a[N],b[N]; int n,k,W,cnt,dc,rt[N],ch[M][2]; ui inc(ui x,ui y){ return x+y>=mod?x+y-mod:x+y; } struct Node{ ui a,b,c,d; Node(){} Node(ui aa,ui bb,ui cc,ui dd){a=aa,b=bb,c=cc,d=dd;} friend Node operator+(Node x,Node y){ return Node(inc(y.a,x.a*y.b%mod),x.b*y.b%mod,inc(x.c+y.c,x.a*y.d%mod),inc(x.d,x.b*y.d%mod)); } }sum[M]; 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; } int newnode(){ int t=dc?dp[dc--]:++tot; return sum[t]=Node(0,1,0,0),t; } void del(int x){ if(!x) return; dp[++dc]=x; del(ls),del(rs); ls=rs=0; } void pushdown(int x){ if(!ls) ls=newnode(); if(!rs) rs=newnode(); sum[ls]=sum[ls]+sum[x]; sum[rs]=sum[rs]+sum[x]; sum[x]=Node(0,1,0,0); } void merge(int &x,int &y){ if(!ch[x][0] and !ch[x][1]) swap(x,y); if(!ch[y][0] and !ch[y][1]) return sum[x]=sum[x]+Node(0,sum[y].a,sum[y].c,0),void(); pushdown(x),pushdown(y); merge(ch[x][0],ch[y][0]),merge(ch[x][1],ch[y][1]); } void modify(int x,int l,int r,int ql,int qr,Node p){ if(ql<=l and r<=qr) return sum[x]=sum[x]+p,void(); int mid=l+r>>1; pushdown(x); if(ql<=mid) modify(ls,l,mid,ql,qr,p); if(mid<qr) modify(rs,mid+1,r,ql,qr,p); } void dfs(int now,int x0,int fa=0){ rt[now]=newnode();sum[rt[now]]=Node(1,0,0,0); for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(to==fa) continue; dfs(to,x0,now); merge(rt[now],rt[to]); del(rt[to]); } modify(rt[now],1,W,1,d[now],Node(0,x0,0,0)); modify(rt[now],1,W,1,W,Node(0,1,0,1)); modify(rt[now],1,W,1,W,Node(1,1,0,0)); } ui query(int x,int l,int r){ if(l==r) return sum[x].c; int mid=l+r>>1; pushdown(x); return (query(ls,l,mid)+query(rs,mid+1,r))%mod; } ui Lagrange(){ in[1]=1; f[0]=1; for(int i=2;i<=n+1;i++) in[i]=(mod-mod/i)*in[mod%i]%mod; for(int i=1;i<=n+1;i++) for(int j=n+1;~j;j--){ if(j) f[j]=inc(f[j-1],f[j]*(mod-i)%mod); else f[j]=f[j]*(mod-i)%mod; } for(int i=1;i<=n+1;i++){ ui res=ans[i]; memcpy(b,f,sizeof 4*(n+2)); for(int j=1;j<=n+1;j++){ if(i==j) continue; if(i>j) res=res*in[i-j]%mod; else res=res*(mod-in[j-i])%mod; } for(int j=0;j<=n+1;j++){ if(!j) b[j]=mod-b[j]*in[i]%mod; else b[j]=inc(mod,b[j-1]-b[j])*in[i]%mod; } for(int j=0;j<=n;j++) a[j]=inc(a[j],b[j]*res%mod); } ui ans=0; for(int i=k;i<=n;i++) ans=inc(ans,a[i]); return ans; } signed main(){ scanf("%d%d%d",&n,&k,&W); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x); for(int i=1;i<=n+1;i++){ dfs(1,i); ans[i]=query(rt[1],1,W); del(rt[1]); } printf("%u\n",Lagrange()); return 0; }