P11032 Develop a Tree
题解 P11032 Develop a Tree
第一次在模拟赛解决绿题，以此纪念。
二分图，看似很高级，实则就是将图中所有点分成两部分，并且每部分之间没有连边，而题目一开始给的是一棵树，因此我们只需要用 dfs 对树进行染色，并且途中维护一个 dp 数组，即可快速求解。
需注意，本题目由于需要求模，所以需要快速幂求解乘法逆元，不会的请跳转P3811 【模板】模意义下的乘法逆元。
（细节见代码）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int qpow(int a, int b, int p);
void dfs(int u, int fa);
struct node {
int w, b; //white black
} dp[N]; //dp[i].b: 以i节点为根节点的子树中黑点的个数（w同理）
int n, m, ans, tmp, k, p, f[N]; //f[i] : i节点的父节点
vector <int> g[N];
bool flag[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
int u, v;
for(int i=1;i<n;i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
for(int i=1;i<=n;i++) {
cin >> p;
ans = 1, tmp = 1, m = dp[i].w % p * (dp[i].b % p) % p;
if(k == 1) {
cout << m % p << ' ';
continue;
}
for(int i=m;i>=m-k+1;i--) ans = i % p * ans % p;
for(int i=1;i<=k;i++) {
tmp = i % p * tmp % p;
}
ans = ans * qpow(tmp, p-2, p) % p;
cout << ans << ' ';
}
return 0;
}
//dfs维护dp
void dfs(int u, int fa) {
f[u] = fa, flag[u] = !flag[fa];
for(auto v : g[u]) {
if(v == fa) continue;
dfs(v, u);
}
if(flag[u]) dp[u].b++;
else dp[u].w++;
dp[fa].b += dp[u].b;
dp[fa].w += dp[u].w;
return ;
}
//快速幂求解乘法逆元
int qpow(int a, int b, int p) {
int res = 1;
while(b) {
if(b & 1) res = res * a % p;
b >>= 1, a = a * a % p;
}
return res;
}
绫地宁宁天下第一可爱！