QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191080 | #5139. DFS Order 2 | chroneZ | ML | 0ms | 0kb | C++17 | 1.8kb | 2023-09-29 17:29:58 | 2023-09-29 17:29:59 |
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 500 + 10, mod = 998244353;
inline int add(int x, int y) {return (x + y >= mod ? x + y - mod : x + y);}
inline int dec(int x, int y) {return (x < y ? x - y + mod : x - y);}
inline void ad(int &x, int y) {x = add(x, y);}
inline void de(int &x, int y) {x = dec(x, y);}
inline int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = 1ll * r * a % mod;
a = 1ll * a * a % mod; b >>= 1;
}
return r;
}
inline int inv(int x) {return qpow(x, mod - 2);}
int fac[N], ifac[N];
inline void fac_init(int n = N - 1) {
fac[0] = 1;
for(int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = inv(fac[n]);
for(int i = n - 1; i >= 0; i--)
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
vector<int> G[N];
int fa[N], siz[N], son[N];
vector<vector<int>> f[N];
int g[N];
void dfs(int u) {
siz[u] = 1; g[u] = 1;
for(auto v : G[u]) {
if(v == fa[u]) continue;
dfs(v); siz[u] += siz[v]; son[u]++;
g[u] = 1ll * g[u] * g[v] % mod;
}
f[u].resize(son[u] + 1, vector<int>(siz[u] + 1, 0));
g[u] = 1ll * g[u] * fac[son[u]] % mod;
}
int F[N][N];
void workf(int u) {
int L0 = 0, L1 = 0;
f[u][0][0] = 1;
for(auto v : G[u]) {
if(v == fa[u]) continue;
workf(v);
for(int i = L0; i >= 0; i--) {
for(int j = L1; j >= 0; j--) {
ad(f[u][i + 1][j + siz[v]], f[u][i][j]);
}
}
L0++, L1 += siz[v];
}
}
void work(int u) {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n; cin >> n;
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs(1); workf(1); work(1);
}
/*
Author: chroneZ
Start thinking at
Start coding at
Finish debugging at
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 1 2 1 3 3 4 3 5