木
弱智 DP 题,直接设 \(f_i\) 表示 \(i\) 子树内染色的方案数,然后每次合并一个点与它的儿子即可(具体而言,因为儿子间独立,所以方案数就是二项式系数)。
需要注意的是因为第一条边可以在任意位置,所以要以每个点为根各 DP 一次。但是这样每条边会被算两次,所以乘以 2 的逆元即可。
时间复杂度 \(O(n^2)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int inv2=5e8+4;
const int N=1e3+100;
int n,res;
int f[N],sz[N],fac[N],inv[N];
vector<int>v[N];
void dfs(int x,int fa){
f[x]=1;
sz[x]=0;
for(auto y:v[x]){
if(y==fa) continue;
dfs(y,x);
f[x]=1ll*f[x]*f[y]%mod*inv[sz[x]]%mod*inv[sz[y]]%mod*fac[sz[x]+sz[y]]%mod;
sz[x]+=sz[y];
}
sz[x]++;
}
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) z=1ll*z*x%mod;
return z;
}
signed main(){
scanf("%lld",&n);
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);
for(int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mod;
for(int i=1,x,y;i<n;i++){
scanf("%lld%lld",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
dfs(i,0);
(res+=f[i])%=mod;
}
printf("%lld\n",1ll*res*inv2%mod);
return 0;
}
标签:sz,const,int,题解,tree,tdpc,1ll,fac,mod
From: https://www.cnblogs.com/xuantianhao/p/17773998.html