https://cf17-exhibition-open.contest.atcoder.jp/tasks/cf17_exhibition_a
包除原理してpathを何本含むかでdpすれば良いということはわかりました。
ただ自信がなく解法見てやっぱり合ってたってなりました。
これ絶対debug時間かかるやつだと思いましたがあっさりサンプル1発で通ってACでした。(謎)
多分包除原理に自信が持てなかったのではと思ってます。包除原理はまず具体的な形で数式を書いて後で同じにできそうなものをまとめるという感じです。あと木dpもあやふやだったので復習しておくと、2つの木のmergeがO(l*r)(lとrは左右の木の大きさ)でできればO(N^3)っぽいけどO(N^2)なやつになります。配列の初期化に注意しなくてはなりませんがO(l+r)は許されると覚えておけばよさそうです。
int N;
vi G[MAX_N];
ll dp[2010][2010][3];
int ts[2010];
void loop(int v) {
int n = sz(G[v]);
ts[v] = 1;
rep(i, 0, n) {
int to = G[v][i];
loop(to);
ts[v] += ts[to];
}
int m = ts[v];
vector<vl> tdp[2] = {vector<vl>(m + 1, vl(3, 0)), vector<vl>(m + 1, vl(3, 0))};
tdp[0][1][0] = 1;
int now = 0, nex = 1;
int cnt = 1;
rep(i, 0, n) {
int to = G[v][i];
rep(j, 0, cnt + ts[to] + 1) {
rep(k, 0, 3) {
tdp[nex][j][k] = 0;
}
}
rep(j, 0, cnt + 1) {
rep(k, 0, ts[to] + 1) {
rep(l, 0, 3) ADD(tdp[nex][j + k][0], tdp[now][j][0] * dp[to][k][l] % mod);
rep(l, 0, 3) ADD(tdp[nex][j + k][1], tdp[now][j][1] * dp[to][k][l] % mod);
rep(l, 0, 3) ADD(tdp[nex][j + k][2], tdp[now][j][2] * dp[to][k][l] % mod);
if(k < ts[to]) {
ADD(tdp[nex][j + k][1], tdp[now][j][0] * dp[to][k + 1][0] % mod * 2 % mod);
ADD(tdp[nex][j + k][1], tdp[now][j][0] * dp[to][k + 1][1] % mod);
ADD(tdp[nex][j + k][2], tdp[now][j][1] * dp[to][k + 1][0] % mod);
ADD(tdp[nex][j + k][2], tdp[now][j][1] * dp[to][k + 1][1] % mod * fiv[2] % mod);
}
}
}
cnt += ts[to];
swap(now, nex);
}
rep(j, 0, m + 1)
rep(k, 0, 3) {
dp[v][j][k] = tdp[now][j][k];
}
}
void solve() {
cin >> N;
C_init(N);
rep(i, 0, N - 1) {
int a; cin >> a; a--;
G[a].pb(i + 1);
}
loop(0);
ll res = 0;
rep(j, 0, N + 1) {
rep(k, 0, 3) {
if((N - j) % 2 == 0) ADD(res, dp[0][j][k] * fac[j] % mod);
else ADD(res, mod - dp[0][j][k] * fac[j] % mod);
}
}
cout << res << "\n";
}
