結果
| 問題 | No.2214 Products on Tree |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2023-02-04 11:55:09 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,688 bytes |
| コンパイル時間 | 368 ms |
| コンパイル使用メモリ | 32,384 KB |
| 実行使用メモリ | 20,976 KB |
| 最終ジャッジ日時 | 2024-07-03 10:22:48 |
| 合計ジャッジ時間 | 5,404 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
15,764 KB |
| testcase_01 | AC | 3 ms
8,820 KB |
| testcase_02 | AC | 2 ms
8,816 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
ソースコード
#include <stdio.h>
#include <stdlib.h>
const int Mod = 998244353;
typedef struct Edge {
struct Edge *next;
int v;
} edge;
int main()
{
int i, N, M, u, w;
edge *adj[200001] = {}, e[400001], *p;
scanf("%d", &N);
for (i = 0; i < N - 1; i++) {
scanf("%d %d", &u, &w);
e[i*2].v = w;
e[i*2+1].v = u;
e[i*2].next = adj[u];
e[i*2+1].next = adj[w];
adj[u] = &(e[i*2]);
adj[w] = &(e[i*2+1]);
}
int par[200001] = {}, q[200001], head, tail;
par[1] = 1;
q[0] = 1;
for (head = 0, tail = 1; head < tail; head++) {
u = q[head];
for (p = adj[u]; p != NULL; p = p->next) {
w = p->v;
if (par[w] == 0) {
par[w] = u;
q[tail++] = w;
}
}
}
int j, ww, size[200001], *dp[200001], a[524288], b[524288], c[524288];
long long tmp;
for (head--; head >= 0; head--) {
u = q[head];
for (p = adj[u], size[u] = 1; p != NULL; p = p->next) {
w = p->v;
if (par[u] == w) continue;
size[u] += size[w];
}
dp[u] = (int*)malloc(sizeof(int) * (size[u] + 1));
dp[u][0] = 0;
dp[u][1] = 1;
for (i = 2; i <= size[u]; i++) dp[u][i] = 0;
size[u] = 1;
for (p = adj[u]; p != NULL; p = p->next) {
w = p->v;
if (par[u] == w) continue;
for (j = 1, tmp = 0; j <= size[w]; j++) tmp += (long long)dp[w][j] * j % Mod;
for (i = size[u], tmp %= Mod; i > 0; i--) {
for (j = 1; j <= size[w]; j++) {
dp[u][i+j] += (long long)dp[u][i] * dp[w][j] % Mod;
if (dp[u][i+j] >= Mod) dp[u][i+j] -= Mod;
}
dp[u][i] = dp[u][i] * tmp % Mod;
}
size[u] += size[w];
free(dp[w]);
}
}
long long ans = 0;
for (i = 1; i <= size[1]; i++) ans += (long long)dp[1][i] * i % Mod;
printf("%lld\n", ans % Mod);
fflush(stdout);
return 0;
}