传送门
初看基本可以确定是个DP,但根本找不到可以当做状态的东西
题解思路的切入点大致是找什么东西是独立的
发现对于一个点,在它的祖先节点还有球的时候,子树外的选法独立,与子树内可以任意合并而不会引起冲突
而当这个节点已经没有球了后,其子树中的选法是独立的,同样可以任意合并而不会引起冲突
于是令 \(r_i\) 为需要额外进入子树多少球,\(s_i\) 为 \(i\) 的子树大小
那对于一个节点 \(i\),其所有子节点 \(j\) 的前 \(r_i\) 次操作可以任意合并,后 \(s_i\) 次操作可以任意合并
一遍树形DP即可
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 1000010 #define ll long long #define fir first #define sec second #define make make_pair // #define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n; int head[N], size, a[N]; const ll mod=1e9+7; struct edge{int to, next;}e[N<<1]; inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;} namespace force{ int fa[N], tot, ans, p[N]; bool s[N]; void solve() { for (int i=2; i<=n; ++i) fa[i]=read(); for (int i=1; i<=n; ++i) a[i]=read(); for (int i=1; i<=n; ++i) if (a[i]) for (int j=1; j<=a[i]; ++j) p[++tot]=i; do { for (int i=1; i<=n; ++i) s[i]=1; for (int i=1; i<=n; ++i) { int now=p[i]; if (!s[now]) goto jump; while (s[fa[now]]) now=fa[now]; s[now]=0; } ++ans; jump: ; } while (next_permutation(p+1, p+n+1)); printf("%d\n", ans); exit(0); } } namespace task{ int r[N], b[N], s[N]; ll dp1[N], dp2[N], fac[N], inv[N]; inline ll C(int n, int k) {return fac[n]*inv[k]%mod*inv[n-k]%mod;} void dfs1(int u) { s[u]=1; b[u]=a[u]; for (int i=head[u],v; ~i; i=e[i].next) { v = e[i].to; dfs1(v); s[u]+=s[v]; b[u]+=b[v]; } r[u]=b[u]-s[u]; } void dfs2(int u) { dp1[u]=dp2[u]=1; int suma=0, sumb=0; for (int i=head[u],v; ~i; i=e[i].next) { v = e[i].to; dfs2(v); dp1[u]=dp1[u]*dp1[v]%mod*C(suma+r[v], r[v])%mod; dp2[u]=dp2[u]*dp2[v]%mod*C(sumb+s[v], s[v])%mod; suma+=r[v]; sumb+=s[v]; } } void solve() { memset(head, -1, sizeof(head)); for (int i=2; i<=n; ++i) add(read(), i); for (int i=1; i<=n; ++i) a[i]=read(); fac[0]=fac[1]=1; inv[0]=inv[1]=1; for (int i=2; i<=n; ++i) fac[i]=fac[i-1]*i%mod; for (int i=2; i<=n; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod; for (int i=2; i<=n; ++i) inv[i]=inv[i-1]*inv[i]%mod; dfs1(1); dfs2(1); // cout<<"dp: "<<dp1[1]<<' '<<dp2[1]<<endl; printf("%lld\n", (dp1[1]*dp2[1])%mod); exit(0); } } signed main() { freopen("ball.in", "r", stdin); freopen("ball.out", "w", stdout); n=read(); // force::solve(); task::solve(); return 0; }