注意到,如果给定每个点的度数 \(d_i\),那么根据 Prufer 序可得,合法本质不同无根树数量为 \(\frac{(n - 2)!}{\prod\limits_{i = 1}^n (d_i - 1)!}\)。
考虑拆贡献,钦定一个点是好点,在这样的基础上求本质不同无根树数量。
设钦定 \(u\) 为好点。那么 \(u\) 子树内所有点都在 \([u, n]\) 内。注意到求无根树的式子只关心树的大小和 \((d_i - 1)!\) 的乘积,并且合法当且仅当 \(\sum (d_i - 1) = n - 2\),于是考虑背包,设 \(f_{i, j, k}\) 为 \([i, n]\) 中,被选的点度数和为 \(j\),数量为 \(k\) 的方案数。
考虑完 \(u\) 子树后,把这些点全部删掉,\(u\) 作为叶子再参与接下来整棵树方案数的计算即可。
时间复杂度 \(O(n^3)\)。
code
// Problem: C - Mex Game on Tree
// Contest: AtCoder - AtCoder Regular Contest 162
// URL: https://atcoder.jp/contests/arc162/tasks/arc162_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1010;
int n, m, a[maxn], rnk[maxn], st[maxn], ed[maxn], times, sz[maxn];
bool flag, ff;
vector<int> G[maxn];
set<int> S[maxn];
void dfs(int u) {
st[u] = ++times;
rnk[times] = u;
sz[u] = (a[u] == -1);
for (int v : G[u]) {
dfs(v);
sz[u] += sz[v];
for (int x : S[v]) {
S[u].insert(x);
}
}
ed[u] = times;
if (a[u] != -1) {
S[u].insert(a[u]);
}
if (sz[u] == 1) {
set<int> T;
for (int i = st[u]; i <= ed[u]; ++i) {
int v = rnk[i];
if (a[v] != -1) {
T.insert(a[v]);
}
}
int mex = 0;
while (T.find(mex) != T.end()) {
++mex;
}
if (mex == m) {
ff = 1;
} else if (mex > m) {
return;
}
for (int i = st[u]; i <= ed[u]; ++i) {
int v = rnk[i];
if (a[v] == -1) {
T.insert(mex);
while (T.find(mex) != T.end()) {
++mex;
}
if (mex == m) {
ff = 1;
}
break;
}
}
} else if (sz[u] == 0) {
int mex = 0;
while (S[u].find(mex) != S[u].end()) {
++mex;
}
if (mex == m) {
ff = 1;
}
}
}
void solve() {
times = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
S[i].clear();
rnk[i] = st[i] = ed[i] = sz[i] = 0;
}
for (int i = 2, p; i <= n; ++i) {
scanf("%d", &p);
G[p].pb(i);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
ff = 0;
dfs(1);
if (ff) {
puts("Alice");
return;
}
puts("Bob");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Smallest Vertices AtCoder Regular Contestsmallest vertices atcoder regular atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest builder atcoder regular contest 163