結果
問題 | No.2504 NOT Path Painting |
ユーザー | yuto1115 |
提出日時 | 2023-10-13 23:20:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 11,368 bytes |
コンパイル時間 | 2,206 ms |
コンパイル使用メモリ | 207,864 KB |
実行使用メモリ | 9,828 KB |
最終ジャッジ日時 | 2024-09-15 19:11:40 |
合計ジャッジ時間 | 5,739 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 99 ms
5,376 KB |
testcase_02 | AC | 100 ms
5,376 KB |
testcase_03 | AC | 99 ms
5,376 KB |
testcase_04 | AC | 99 ms
5,376 KB |
testcase_05 | AC | 100 ms
5,376 KB |
testcase_06 | AC | 100 ms
5,376 KB |
testcase_07 | AC | 100 ms
5,376 KB |
testcase_08 | AC | 100 ms
5,376 KB |
testcase_09 | AC | 99 ms
5,376 KB |
testcase_10 | AC | 99 ms
5,376 KB |
testcase_11 | AC | 100 ms
5,376 KB |
testcase_12 | AC | 100 ms
5,376 KB |
testcase_13 | AC | 121 ms
5,376 KB |
testcase_14 | AC | 121 ms
5,376 KB |
testcase_15 | AC | 135 ms
5,748 KB |
testcase_16 | AC | 139 ms
5,744 KB |
testcase_17 | AC | 139 ms
5,704 KB |
testcase_18 | AC | 124 ms
6,056 KB |
testcase_19 | AC | 146 ms
9,312 KB |
testcase_20 | AC | 129 ms
9,828 KB |
ソースコード
#include<bits/stdc++.h> #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) #define SORT(a) sort(all(a)); #define REV(a) reverse(all(a)); #define SZ(a) int(a.size()) #define popcount(x) __builtin_popcountll(x) #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define ppf pop_front #define ppb pop_back #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0); #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using ll = long long; using ld = long double; using P = pair<int, int>; using LP = pair<ll, ll>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vd = vector<double>; using vvd = vector<vd>; using vs = vector<string>; using vc = vector<char>; using vvc = vector<vc>; using vb = vector<bool>; using vvb = vector<vb>; using vp = vector<P>; using vvp = vector<vp>; using vlp = vector<LP>; using vvlp = vector<vlp>; template<class T> using PQ = priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>; template<class S, class T> istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; } template<class S, class T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; } template<class S, class T, class U> istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template<class S, class T, class U> ostream &operator<<(ostream &os, const tuple<S, T, U> &t) { return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}'; } template<class T> istream &operator>>(istream &is, vector<T> &v) { for (T &t: v) { is >> t; } return is; } template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { os << '['; rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template<class T> ostream &operator<<(ostream &os, const deque<T> &v) { os << '['; rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template<class T> ostream &operator<<(ostream &os, const set<T> &st) { os << '{'; auto it = st.begin(); while (it != st.end()) { os << (it == st.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template<class T> ostream &operator<<(ostream &os, const multiset<T> &st) { os << '{'; auto it = st.begin(); while (it != st.end()) { os << (it == st.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template<class T, class U> ostream &operator<<(ostream &os, const map<T, U> &mp) { os << '{'; auto it = mp.begin(); while (it != mp.end()) { os << (it == mp.begin() ? "" : ", ") << *it; it++; } return os << '}'; } template<class T> void vecout(const vector<T> &v, char div = '\n') { rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div); } template<class T> bool constexpr chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool constexpr chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void scan() {} template<class Head, class... Tail> void scan(Head &head, Tail &... tail) { cin >> head; scan(tail...); } template<class T> void print(const T &t) { cout << t << '\n'; } template<class Head, class... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template<class... T> void fin(const T &... a) { print(a...); exit(0); } template<class T> vector<T> &operator+=(vector<T> &v, T x) { for (T &t: v) t += x; return v; } template<class T> vector<T> &operator-=(vector<T> &v, T x) { for (T &t: v) t -= x; return v; } template<class T> vector<T> &operator*=(vector<T> &v, T x) { for (T &t: v) t *= x; return v; } template<class T> vector<T> &operator/=(vector<T> &v, T x) { for (T &t: v) t /= x; return v; } struct Init_io { Init_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << boolalpha << fixed << setprecision(15); cerr << boolalpha << fixed << setprecision(15); } } init_io; const string yes[] = {"no", "yes"}; const string Yes[] = {"No", "Yes"}; const string YES[] = {"NO", "YES"}; const int inf = 1001001001; const ll linf = 1001001001001001001; void rearrange(const vi &) {} template<class T, class... Tail> void rearrange(const vi &ord, vector<T> &head, Tail &...tail) { assert(ord.size() == head.size()); vector<T> ori = head; rep(i, ord.size()) head[i] = ori[ord[i]]; rearrange(ord, tail...); } template<class T, class... Tail> void sort_by(vector<T> &head, Tail &... tail) { vi ord(head.size()); iota(all(ord), 0); sort(all(ord), [&](int i, int j) { return head[i] < head[j]; }); rearrange(ord, head, tail...); } bool in_rect(int i, int j, int h, int w) { return 0 <= i and i < h and 0 <= j and j < w; } template<class T, class S> vector<T> cumsum(const vector<S> &v, bool shift_one = true) { int n = v.size(); vector<T> res; if (shift_one) { res.resize(n + 1); rep(i, n) res[i + 1] = res[i] + v[i]; } else { res.resize(n); if (n) { res[0] = v[0]; rep(i, 1, n) res[i] = res[i - 1] + v[i]; } } return res; } vvi graph(int n, int m, bool directed = false, int origin = 1) { vvi G(n); rep(_, m) { INT(u, v); u -= origin, v -= origin; G[u].pb(v); if (!directed) G[v].pb(u); } return G; } template<class T> vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) { vector<vector<pair<int, T>>> G(n); rep(_, m) { int u, v; T w; scan(u, v, w); u -= origin, v -= origin; G[u].eb(v, w); if (!directed) G[v].eb(u, w); } return G; } template<int mod> class modint { ll x; public: constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {} static constexpr int get_mod() { return mod; } constexpr int val() const { return x; } constexpr modint operator-() const { return modint(-x); } constexpr modint &operator+=(const modint &a) { if ((x += a.val()) >= mod) x -= mod; return *this; } constexpr modint &operator++() { return *this += 1; } constexpr modint &operator-=(const modint &a) { if ((x += mod - a.val()) >= mod) x -= mod; return *this; } constexpr modint &operator--() { return *this -= 1; } constexpr modint &operator*=(const modint &a) { (x *= a.val()) %= mod; return *this; } constexpr modint operator+(const modint &a) const { modint res(*this); return res += a; } constexpr modint operator-(const modint &a) const { modint res(*this); return res -= a; } constexpr modint operator*(const modint &a) const { modint res(*this); return res *= a; } constexpr modint pow(ll t) const { modint res = 1, a(*this); while (t > 0) { if (t & 1) res *= a; t >>= 1; a *= a; } return res; } template<int m> friend istream &operator>>(istream &, modint<m> &); // for prime mod constexpr modint inv() const { return pow(mod - 2); } constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); } constexpr modint operator/(const modint &a) const { modint res(*this); return res /= a; } // constraints : mod = 2 or val = 0 or val^((mod-1)/2) ≡ 1 // mod is prime // time complexity : O(log^2 p) // reference : https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp modint sqrt() const { if (x < 2) return x; assert(this->pow((mod - 1) >> 1).val() == 1); modint b = 1; while (b.pow((mod - 1) >> 1).val() == 1) b += 1; ll m = mod - 1, e = 0; while (~m & 1) m >>= 1, e += 1; modint X = this->pow((m - 1) >> 1); modint Y = (*this) * X * X; X *= *this; modint Z = b.pow(m); while (Y.val() != 1) { ll j = 0; modint t = Y; while (t.val() != 1) { j += 1; t *= t; } Z = Z.pow(1LL << (e - j - 1)); X *= Z; Z *= Z; Y *= Z; e = j; } return X; } }; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; template<int mod> istream &operator>>(istream &is, modint<mod> &a) { return is >> a.x; } template<int mod> constexpr ostream &operator<<(ostream &os, const modint<mod> &a) { return os << a.val(); } template<int mod> constexpr bool operator==(const modint<mod> &a, const modint<mod> &b) { return a.val() == b.val(); } template<int mod> constexpr bool operator!=(const modint<mod> &a, const modint<mod> &b) { return a.val() != b.val(); } template<int mod> constexpr modint<mod> &operator++(modint<mod> &a) { return a += 1; } template<int mod> constexpr modint<mod> &operator--(modint<mod> &a) { return a -= 1; } using mint = modint998244353; using vm = vector<mint>; using vvm = vector<vm>; void solve() { INT(n); vvi G = graph(n, n - 1); int all = n * (n + 1) / 2; mint ans = 1; vi sz(n, 1); auto f = [&](int tmp) -> mint { return mint(tmp) / (all - tmp); }; auto dfs = [&](auto &dfs, int u, int p) -> void { int sum = 0; for (int v: G[u]) { if (v == p) continue; dfs(dfs, v, u); sz[u] += sz[v]; sum += sz[v] * (sz[v] + 1) / 2; ans -= f(sz[v] * (n - sz[v])); } sum += (n - sz[u]) * (n - sz[u] + 1) / 2; ans += f(all - sum); }; dfs(dfs, 0, -1); print(ans); } int main() { INT(t); rep(_, t) solve(); // vd dp(10); // dp[1] = 1; // rep(i, 2, 10) { // dp[i] = 1; // rep(j, 1, i) dp[i] -= dp[j] * (i - j + 1); // } // print(dp); }