QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191080#5139. DFS Order 2chroneZML 0ms0kbC++171.8kb2023-09-29 17:29:582023-09-29 17:29:59

Judging History

你现在查看的是最新测评结果

  • [2023-09-29 17:29:59]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-09-29 17:29:58]
  • 提交

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 
*/

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

5
1 2
1 3
3 4
3 5

output:


result: