This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define N 4000
#define MD 1000000007
int vv[N + 1], ff[N + 1], gg[N + 1];
void init() {
int i;
ff[0] = gg[0] = 1;
for (i = 1; i <= N; i++) {
vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
ff[i] = (long long) ff[i - 1] * i % MD;
gg[i] = (long long) gg[i - 1] * vv[i] % MD;
}
}
int choose(int n, int k) {
return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}
int ll[N + 1], rr[N + 1], sz[N + 1], kk[N + 1], sz[N + 1], cc[N + 1], dp[N + 1][N + 1];
void dfs(int i, int d) {
int l = ll[i], r = rr[i], c, kl, kr, x, y, tmp;
if (i == 0)
return;
dfs(l, 0);
dfs(r, 1);
if (d == 1)
tmp = l, l = r, r = tmp;
sz[i] = sz[l] + sz[r] + 1, cc[i] = cc[l] + cc[r] + 1 - kk[i];
for (c = 0; c <= cc[i]; c++) {
x = 0;
for (kl = 0; kl <= kk[i]; kl++) {
kr = kk[i] - kl;
if (kl <= cc[l] && kr <= cc[r]) {
y = choose(kk[i], kl);
if (c <= cc[l] - kl)
y = (long long) y * dp[l][c + kl] % MD * dp[r][kr] % MD;
else {
y = (long long) y * choose(c, cc[l] - kl) % MD;
if (c < cc[i])
y = (long long) y * dp[l][cc[l]] % MD * dp[r][c + kk[i] - cc[l]] % MD;
else {
y = (long long) y * (c - cc[l] + kl) % MD;
y = (long long) y * dp[l][cc[l]] % MD * dp[r][cc[r]] % MD;
}
}
x = (x + y) % MD;
}
if (c == cc[i]) {
kr = kk[i] - kl - 1;
if (kl <= cc[l] && kr <= cc[r]) {
y = (long long) choose(kk[i], kl) * (kk[i] - kl) % MD;
y = (long long) y * choose(c, cc[l] - kl) % MD;
y = (long long) y * dp[l][cc[l]] % MD * dp[r][cc[r]] % MD;
x = (x + y) % MD;
}
}
}
dp[i][c] = x;
}
}
int main() {
int n, k, i;
init();
scanf("%d%d", &n, &k);
if (k > n) {
printf("0\n");
return 0;
}
while (k--) {
scanf("%d", &i);
kk[i]++;
}
for (i = 1; i <= n; i++)
scanf("%d%d", &ll[i], &rr[i]);
sz[0] = 0, cc[0] = 0, dp[0][0] = 1;
dfs(1, 0);
printf("%d\n", dp[1][0]);
return 0;
}
Compilation message (stderr)
Main.c: In function 'main':
Main.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d", &i);
| ^~~~~~~~~~~~~~~
Main.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d%d", &ll[i], &rr[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |