Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <fstream>
- #include <stdio.h>
- #include <string>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <ctime>
- #include <cstring>
- #include <iomanip>
- #include <random>
- #include <unordered_set>
- #include <unordered_map>
- #include <deque>
- #include <queue>
- #include <bitset>
- #include <sstream>
- #include <cassert>
- #include <complex>
- using namespace std;
- #define mp make_pair
- #define X first
- #define Y second
- #define all(x) x.begin(), x.end()
- #define all_(x) x.rbegin(), x.rend()
- #define multi_test 0
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef pair<ld, ld> pld;
- typedef complex<ld> base;
- const int INF = 2e9 + 9;
- const ll INF1 = 8e18 + 9;
- const ll MAXN = 3e5 + 7;
- const ll MAXN1 = 1 << 10;
- const ll MAXN2 = 55 * MAXN;
- const ll MOD = 998244353;
- const ll MOD1 = 1e9 + 9;
- const ll ALPH = 27;
- const ll PW1 = 2;
- const ll PW2 = 199;
- const ll PW3 = 193;
- const ll PW4 = 117;
- const ld EPS = 1e-7;
- const ll BLOCK = 316;
- const ll BLOCK1 = 1 << 9;
- const ull T = 3e9 + 239;
- void solve();
- signed main(){
- srand('a' + 'l' + 'e' + 'x' + 'X' + '5' + '1' + '2');
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifdef _DEBUG
- #define MAXN 5000
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif // _DEBUG
- int q = 1;
- if (multi_test) cin >> q;
- while (q--) solve();
- }
- /*------------------------------------------------------------------------------------------------------------*/
- vector<pii> g[MAXN];
- ll dp[MAXN1][MAXN1], tmp[MAXN1][MAXN1], cnt[MAXN1], c[MAXN1][MAXN1];
- ll fc[MAXN];
- ll bin_pow(ll a, ll k) {
- if (k == 0) return 1;
- if (k % 2 == 0) return bin_pow(a * a % MOD, k / 2);
- return (bin_pow(a, k - 1) * a) % MOD;
- }
- ll inv(ll x) {
- return bin_pow(x, MOD - 2);
- }
- ll f(ll x, ll y) {
- return c[x + y][x];
- }
- void add(ll &a, ll b) {
- a = (a + b) % MOD;
- }
- ll mult(ll a, ll b) {
- return (a * b) % MOD;
- }
- void dfs(int vert, int p = -1) {
- dp[vert][0] = 1;
- cnt[vert] = 1;
- for (auto &i : g[vert]) {
- if (i.X == p) continue;
- dfs(i.X, vert);
- for (int j = 0; j < cnt[vert] + cnt[i.X]; ++j) {
- tmp[vert][j] = 0;
- for (int a = 0; a < min<ll>(cnt[vert], j + 1); ++a) {
- if (i.Y == 1) {
- for (int b = j - a; b < cnt[i.X]; ++b) {
- add(tmp[vert][j], mult(mult(mult(dp[vert][a], dp[i.X][b]), f(a, j - a)), f(cnt[vert] - a - 1, cnt[i.X] - j + a)));
- }
- }
- else {
- for (int b = 0; b < j - a; ++b) {
- add(tmp[vert][j], mult(mult(mult(dp[vert][a], dp[i.X][b]), f(a, j - a)), f(cnt[vert] - a - 1, cnt[i.X] - j + a)));
- }
- }
- }
- }
- for (int j = 0; j < cnt[vert] + cnt[i.X]; ++j) {
- dp[vert][j] = tmp[vert][j];
- }
- cnt[vert] += cnt[i.X];
- }
- }
- void solve() {
- fc[0] = 1;
- for (ll i = 1; i < MAXN; ++i) fc[i] = (fc[i - 1] * i) % MOD;
- for (int i = 0; i < MAXN1; ++i) {
- for (int j = 0; j <= i; ++j) {
- c[i][j] = fc[i] * inv(fc[i - j] * fc[j] % MOD) % MOD;
- }
- }
- int n;
- cin >> n;
- for (int i = 1; i < n; ++i) {
- int a, b;
- cin >> a >> b;
- g[a].emplace_back(b, 1);
- g[b].emplace_back(a, 0);
- }
- dfs(1);
- ll ans = 0;
- for (int i = 0; i < n; ++i) add(ans, dp[1][i]);
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement