結果
問題 | No.2504 NOT Path Painting |
ユーザー |
|
提出日時 | 2023-10-13 22:23:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 6,156 bytes |
コンパイル時間 | 1,200 ms |
コンパイル使用メモリ | 126,276 KB |
最終ジャッジ日時 | 2025-02-17 07:22:31 |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:273:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 273 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:278:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 278 | scanf("%d%d", &v, &u); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:308:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 308 | scanf("%d", &t); | ~~~~~^~~~~~~~~~
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC target("avx,avx2,fma")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <ctime>#include <cassert>#include <complex>#include <string>#include <cstring>#include <chrono>#include <random>#include <bitset>#include <array>#include <climits>using namespace std;#ifdef LOCAL#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}#else#define eprintf(...) 42#endifusing ll = long long;using ld = long double;using uint = unsigned int;using ull = unsigned long long;using pii = pair<int, int>;using pli = pair<ll, int>;using pll = pair<ll, ll>;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) {return (ull)rng() % B;}#define mp make_pair#define all(x) (x).begin(),(x).end()clock_t startTime;double getCurrentTime() {return (double)(clock() - startTime) / CLOCKS_PER_SEC;}ll floor_div(ll x, ll y) {assert(y != 0);if (y < 0) {y = -y;x = -x;}if (x >= 0) return x / y;return (x + 1) / y - 1;}ll ceil_div(ll x, ll y) {assert(y != 0);if (y < 0) {y = -y;x = -x;}if (x <= 0) return x / y;return (x - 1) / y + 1;}const uint MOD = 998244353;template<uint mod = MOD> struct mint { // 1000000007 1000000009uint x;mint() : x(0) {}mint(ll _x) {_x %= mod;if (_x < 0) _x += mod;x = _x;}mint& operator += (const mint &a) {x += a.x;if (x >= mod) x -= mod;return *this;}mint& operator -= (const mint &a) {x += mod - a.x;if (x >= mod) x -= mod;return *this;}mint& operator *= (const mint &a) {x = (ull)x * a.x % mod;return *this;}mint pow(ll pw) const {mint res = 1;mint cur = *this;while(pw) {if (pw & 1) res *= cur;cur *= cur;pw >>= 1;}return res;}mint inv() const {assert(x != 0);uint t = x;uint res = 1;while(t != 1) {uint z = mod / t;res = (ull)res * (mod - z) % mod;t = mod - t * z;}return res;}mint& operator /= (const mint &a) {return *this *= a.inv();}mint operator + (const mint &a) const {return mint(*this) += a;}mint operator - (const mint &a) const {return mint(*this) -= a;}mint operator * (const mint &a) const {return mint(*this) *= a;}mint operator / (const mint &a) const {return mint(*this) /= a;}bool sqrt(mint &res) const {if (mod == 2 || x == 0) {res = *this;return true;}if (pow((mod - 1) / 2) != 1) return false;if (mod % 4 == 3) {res = pow((mod + 1) / 4);return true;}int pw = (mod - 1) / 2;int K = 30;while((1 << K) > pw) K--;while(true) {mint t = myRand(mod);mint a = 0, b = 0, c = 1;for (int k = K; k >= 0; k--) {a = b * b;b = b * c * 2;c = c * c + a * *this;if (((pw >> k) & 1) == 0) continue;a = b;b = b * t + c;c = c * t + a * *this;}if (b == 0) continue;c -= 1;c *= mint() - b.inv();if (c * c == *this) {res = c;return true;}}assert(false);}bool operator == (const mint &a) const {return x == a.x;}bool operator != (const mint &a) const {return x != a.x;}bool operator < (const mint &a) const {return x < a.x;}};template<uint mod = MOD> struct Factorials {using Mint = mint<mod>;vector<Mint> f, fi;Factorials() : f(), fi() {}Factorials(int n) {n += 10;f = vector<Mint>(n);fi = vector<Mint>(n);f[0] = 1;for (int i = 1; i < n; i++)f[i] = f[i - 1] * i;fi[n - 1] = f[n - 1].inv();for (int i = n - 1; i > 0; i--)fi[i - 1] = fi[i] * i;}Mint C(int n, int k) {if (k < 0 || k > n) return 0;return f[n] * fi[k] * fi[n - k];}};template<uint mod = MOD> struct Powers {using Mint = mint<mod>;vector<Mint> p, pi;Powers() : p(), pi() {}Powers(int n, Mint x) {n += 10;if (x == 0) {p = vector<Mint>(n);p[0] = 1;} else {p = vector<Mint>(n);pi = vector<Mint>(n);p[0] = pi[0] = 1;Mint xi = x.inv();for (int i = 1; i < n; i++) {p[i] = p[i - 1] * x;pi[i] = pi[i - 1] * xi;}}}Mint pow(int n) {if (n >= 0)return p[n];elsereturn pi[-n];}};template<uint mod = MOD> struct Inverses {using Mint = mint<mod>;vector<Mint> ii;Inverses() : ii() {}Inverses(int n) {n += 10;ii = vector<Mint>(n);ii[1] = 1;for (int x = 2; x < n; x++)ii[x] = Mint() - ii[mod % x] * (mod / x);}Mint inv(Mint x) {assert(x != 0);uint t = x.x;uint res = 1;while(t >= (int)ii.size()) {uint z = mod / t;res = (ull)res * (mod - z) % mod;t = mod - t * z;}return ii[t] * res;}};using Mint = mint<>;const int N = 200200;int n;vector<int> g[N];int sz[N];void dfs(int v, int par) {sz[v] = 1;for (int u : g[v]) if (u != par) {dfs(u, v);sz[v] += sz[u];}}void solve() {scanf("%d", &n);for (int i = 0; i < n; i++)g[i].clear();for (int i = 1; i < n; i++) {int v, u;scanf("%d%d", &v, &u);v--;u--;g[v].push_back(u);g[u].push_back(v);}dfs(0, -1);Mint ans = 0;for (int v = 0; v < n; v++) {Mint p = 0;int sum = n - 1;for (int u : g[v]) if (sz[u] < sz[v]) {p += sz[u] * (sz[u] + 1);sum -= sz[u];}p += sum * (sum + 1);ans += Mint(n) * (n + 1) / p;if (v != 0) {p = n * (n + 1) - sz[v] * (n - sz[v]) * 2;ans -= Mint(n) * (n + 1) / p;}}printf("%u\n", ans.x);}int main() {startTime = clock();// freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);int t;scanf("%d", &t);for (int i = 1; i <= t; i++) {eprintf("--- Case #%d start ---\n", i);//printf("Case #%d: ", i);solve();//printf("%lld\n", (ll)solve());/*if (solve()) {printf("Yes\n");} else {printf("No\n");}*/eprintf("--- Case #%d end ---\n", i);eprintf("time = %.5lf\n", getCurrentTime());eprintf("++++++++++++++++++++\n");}return 0;}