Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
41454 baka24 【BJ】T3 C++ 解答错误 90 737 MS 2344 KB 2130 2026-04-24 15:42:46

Tests(18/20):


#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v const int MAXN=510,Mod=998244353; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int n,m,k,q,a[MAXN]; int f[MAXN][MAXN],g[MAXN],jc[MAXN],ny[MAXN],p[MAXN],s[MAXN<<1],t[MAXN]; int qry(int x,int y){ int res=0; int tmp=1; for(int i=0;i<=m;i++){ res+=tmp*s[i+y]%Mod*g[i]%Mod; tmp=tmp*(x-i)%Mod; } res=res%Mod; return res; } int siz[MAXN]; void dfs(int u,int lst){ for(inx(u))if(v!=lst)dfs(v,u); for(int i=1;i<=m;i++)g[i]=0; g[0]=1; for(inx(u))if(v!=lst){ for(int i=m;i>=0;i--)if(g[i]){ int tmp=g[i];g[i]=0; for(int j=0;j<=m;j++)g[i+j]+=tmp*f[v][j]%Mod; } for(int i=0;i<=m;i++)g[i]%=Mod; } for(int i=1;i<=m;i++)add(g[i],g[i-1]); for(int i=0;i<=m;i++)g[i]=g[i]*p[i]%Mod; s[2*m+1]=1; for(int i=2*m;i>=0;i--)s[i]=s[i+1]*(a[u]+m-i+Mod)%Mod; for(int i=0;i<=m;i++)f[u][i]=i+a[u]<=m?g[i]*Pow(p[i],Mod-2)%Mod:qry(i+a[u],m+1-i)*Pow(s[2*m-i+1],Mod-2)%Mod; } void slv(){ n=read(); for(int i=2;i<=n;i++)add_side(i,read()); for(int i=1;i<=n;i++)a[i]=read(); m=n; jc[0]=ny[0]=1; for(int i=1;i<=m;i++)jc[i]=jc[i-1]*i%Mod,ny[i]=Pow(jc[i],Mod-2); for(int i=0;i<=m;i++)p[i]=ny[i]%Mod*((m-i)&1?Mod-ny[m-i]:ny[m-i])%Mod; dfs(1,1); printf("%lld",f[1][0]); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }


测评信息: