牛客挑战赛30 小G砍树 树形dp

小G砍树

dfs两次, dp出每个点作为最后一个点的方案数。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = ;
const double eps = 1e-;
const double PI = acos(-); int n, ans, son[N], dp[N];
vector<int> G[N]; int F[N], Finv[N], inv[N]; void init() {
inv[] = F[] = Finv[] = ;
for(int i = ; i < N; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for(int i = ; i < N; i++) F[i] = 1ll * F[i - ] * i % mod;
for(int i = ; i < N; i++) Finv[i] = 1ll * Finv[i - ] * inv[i] % mod;
} int Power(int a, int b) {
int ans = ;
while(b) {
if(b & ) ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod; b >>= ;
}
return ans;
} void dfs(int u, int fa) {
dp[u] = ;
for(auto& v : G[u]) {
if(v == fa) continue;
dfs(v, u);
dp[u] = 1ll * dp[u] * dp[v] % mod;
dp[u] = 1ll * dp[u] * Finv[son[v]] % mod;
son[u] += son[v];
}
dp[u] = 1ll * dp[u] * F[son[u]] % mod;
son[u]++;
} void getAns(int u, int fa, int tmp) {
ans = (ans + 1ll * tmp * dp[u] % mod * F[n - ] % mod * Finv[son[u] - ] % mod * Finv[n - son[u]] % mod) % mod;
tmp = 1ll * tmp * Finv[n - son[u]] % mod;
for(auto& v : G[u]) {
if(v == fa) continue;
tmp = 1ll * tmp * dp[v] % mod;
tmp = 1ll * tmp * Finv[son[v]] % mod;
}
for(auto& v : G[u]) {
if(v == fa) continue;
int nxttmp = 1ll * tmp * F[son[v]] % mod * F[n - son[v] - ] % mod * Power(dp[v], mod - ) % mod;
getAns(v, u, nxttmp);
}
} int main() {
init();
scanf("%d", &n);
for(int i = ; i <= n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, );
getAns(, , );
printf("%d\n", ans);
return ;
} /*
*/
上一篇:Python对象的创建和赋值


下一篇:angularjs指令中的compile与link函数详解