結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-05-14 22:25:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 136 ms / 2,000 ms |
コード長 | 19,905 bytes |
コンパイル時間 | 2,362 ms |
コンパイル使用メモリ | 211,332 KB |
最終ジャッジ日時 | 2025-01-21 11:32:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
コンパイルメッセージ
main.cpp:380:59: note: ‘#pragma message: [REFS] Xoshiro: https://prng.di.unimi.it’ 380 | #pragma message("[REFS] Xoshiro: https://prng.di.unimi.it") | ^
ソースコード
#include <bits/stdc++.h>#include <iostream>#pragma region Header#pragma GCC target("avx2")#pragma GCC optimize("unroll-loops")#pragma region TypeAliasusing i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;using f64 = double;using f80 = long double;using f128 = __float128;constexpr i32 operator"" _i32(u64 v){return v;}constexpr u32 operator"" _u32(u64 v){return v;}constexpr i64 operator"" _i64(u64 v){return v;}constexpr u64 operator"" _u64(u64 v){return v;}constexpr f64 operator"" _f64(f80 v){return v;}constexpr f80 operator"" _f80(f80 v){return v;}using Istream = std::istream;using Ostream = std::ostream;using Str = std::string;template<typename T>using Lt = std::less<T>;template<typename T>using Gt = std::greater<T>;template<typename T>using IList = std::initializer_list<T>;template<int n>using BSet = std::bitset<n>;template<typename T1, typename T2>using Pair = std::pair<T1, T2>;template<typename... Ts>using Tup = std::tuple<Ts...>;template<typename T, int N>using Arr = std::array<T, N>;template<typename... Ts>using Deq = std::deque<Ts...>;template<typename... Ts>using Set = std::set<Ts...>;template<typename... Ts>using MSet = std::multiset<Ts...>;template<typename... Ts>using USet = std::unordered_set<Ts...>;template<typename... Ts>using UMSet = std::unordered_multiset<Ts...>;template<typename... Ts>using Map = std::map<Ts...>;template<typename... Ts>using MMap = std::multimap<Ts...>;template<typename... Ts>using UMap = std::unordered_map<Ts...>;template<typename... Ts>using UMMap = std::unordered_multimap<Ts...>;template<typename... Ts>using Vec = std::vector<Ts...>;template<typename... Ts>using Stack = std::stack<Ts...>;template<typename... Ts>using Que = std::queue<Ts...>;template<typename T>using MaxHeap = std::priority_queue<T>;template<typename T>using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>;#pragma endregion#pragma region Constantstemplate<typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template<typename T>constexpr T PI = T{3.141592653589793238462643383279502884};template<typename T = u64>constexpr T TEN(const int n){return n == 0 ? T{1} : TEN<T>(n - 1) * T{10};}#pragma endregion#pragma region FuncAliastemplate<typename T>bool chmin(T& a, const T& b){if (a > b) {a = b;return true;} else {return false;}}template<typename T>bool chmax(T& a, const T& b){if (a < b) {a = b;return true;} else {return false;}}template<typename T>T fdiv(T x, T y){if (y < T{}) { x = -x, y = -y; }return x >= T{} ? x / y : (x - y + 1) / y;}template<typename T>T cdiv(T x, T y){if (y < T{}) { x = -x, y = -y; }return x >= T{} ? (x + y - 1) / y : x / y;}template<typename T, typename I>T power(T v, I n){T ans = 1;for (; n > 0; n >>= 1, v *= v) {if (n % 2 == 1) { ans *= v; }}return ans;}template<typename T, typename I>T power(T v, I n, const T& e){T ans = e;for (; n > 0; n >>= 1, v *= v) {if (n % 2 == 1) { ans *= v; }}return ans;}template<typename T>void fillAll(Vec<T>& vs, const T& v){std::fill(vs.begin(), vs.end(), v);}template<typename T, typename C = Lt<T>>void sortAll(Vec<T>& vs, C comp = C{}){std::sort(vs.begin(), vs.end(), comp);}template<typename T>void reverseAll(Vec<T>& vs){std::reverse(vs.begin(), vs.end());}template<typename T>void uniqueAll(Vec<T>& vs){sortAll(vs);vs.erase(std::unique(vs.begin(), vs.end()), vs.end());}template<typename T>void iotaAll(Vec<T>& vs, T offset = T{}){std::iota(vs.begin(), vs.end(), offset);}template<typename T, typename V = T>V sumAll(const Vec<T>& vs){return std::accumulate(vs.begin(), vs.end(), V{});}template<typename T>int minInd(const Vec<T>& vs){return std::min_element(vs.begin(), vs.end()) - vs.begin();}template<typename T>int maxInd(const Vec<T>& vs){return std::max_element(vs.begin(), vs.end()) - vs.begin();}template<typename T>int lbInd(const Vec<T>& vs, const T& v){return std::lower_bound(vs.begin(), vs.end(), v) - vs.begin();}template<typename T>int ubInd(const Vec<T>& vs, const T& v){return std::lower_bound(vs.begin(), vs.end(), v) - vs.begin();}template<typename T, typename F>Vec<T> genVec(int n, F gen){Vec<T> ans;std::generate_n(std::back_insert_iterator(ans), n, gen);return ans;}template<typename T>Vec<T> iotaVec(int n, T offset = T{}){Vec<T> ans(n);iotaAll(ans, offset);return ans;}template<typename T, typename F = Lt<T>>Vec<T> iotaVec(const Vec<T>& vs, F comp = F{}){auto is = iotaVec(vs.size(), 0);sortAll(is, [&](int i, int j) { return comp(vs[i], vs[j]); });return is;}template<typename T>Vec<T> operator+=(Vec<T>& vs1, const Vec<T>& vs2){vs1.insert(vs1.end(), vs2.begin(), vs2.end());return vs1;}template<typename T>Vec<T> operator+(const Vec<T>& vs1, const Vec<T>& vs2){return Vec<T>{vs1} += vs2;}#pragma endregion#pragma region Show#pragma endregion#pragma region BitOpsconstexpr int popcount(const u64 v){return v ? __builtin_popcountll(v) : 0;}constexpr int log2p1(const u64 v){return v ? 64 - __builtin_clzll(v) : 0;}constexpr int lsbp1(const u64 v){return __builtin_ffsll(v);}constexpr int clog(const u64 v){return v ? log2p1(v - 1) : 0;}constexpr u64 ceil2(const u64 v){return 1_u64 << clog(v);}constexpr u64 floor2(const u64 v){return v ? (1_u64 << (log2p1(v) - 1)) : 0_u64;}constexpr bool ispow2(const u64 v){return (v & (v - 1)) == 0;}constexpr bool btest(const u64 mask, const int ind){return (mask >> ind) & 1_u64;}#pragma endregion#pragma region FixPointtemplate<typename F>struct Fixpoint : F{Fixpoint(F&& f) : F{std::forward<F>(f)} {}template<typename... Args>auto operator()(Args&&... args) const{return F::operator()(*this, std::forward<Args>(args)...);}};#pragma endregion#pragma region NdVectemplate<typename T, int n, int i = 0>auto ndVec(int const (&szs)[n], const T x = T{}){if constexpr (i == n) {return x;} else {return std::vector(szs[i], ndVec<T, n, i + 1>(szs, x));}}#pragma endregion#pragma region Rangeclass range{private:struct itr{itr(int start = 0, int step = 1) : m_cnt{start}, m_step{step} {}bool operator!=(const itr& it) const{return m_cnt != it.m_cnt;}int operator*(){return m_cnt;}itr& operator++(){m_cnt += m_step;return *this;}int m_cnt, m_step;};int m_start, m_end, m_step;public:range(int start, int end, int step = 1): m_start{start}, m_end{end}, m_step{step}{assert(m_step == 1 or m_step == -1);}itr begin() const{return itr{m_start, m_step};}itr end() const{return itr{m_end, m_step};}};range rep(int end){return range(0, end, 1);}range per(int rend){return range(rend - 1, -1, -1);}class ndRep{private:struct itr{itr(const Vec<int>& ns) : m_ns{ns}, m_cs(ns.size(), 0), m_end{false} {}bool operator!=(const itr&) const{return not m_end;}const Vec<int>& operator*(){return m_cs;}itr& operator++(){for (const int i : per(m_ns.size())) {m_cs[i]++;if (m_cs[i] < m_ns[i]) {break;} else {if (i == 0) { m_end = true; }m_cs[i] = 0;}}return *this;}Vec<int> m_ns, m_cs;bool m_end;};Vec<int> m_ns;public:ndRep(const Vec<int>& ns) : m_ns{ns} {}itr begin() const{return itr{m_ns};}itr end() const{return itr{m_ns};}};#pragma endregion#pragma message("[REFS] Xoshiro: https://prng.di.unimi.it")#pragma region Xoshironamespace xoshiro_impl {u64 x;u64 next(){uint64_t z = (x += 0x9e3779b97f4a7c15);z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;z = (z ^ (z >> 27)) * 0x94d049bb133111eb;return z ^ (z >> 31);}}class Xoshiro32{public:using result_type = u32;using T = result_type;Xoshiro32(T seed = 0){xoshiro_impl::x = seed;s[0] = xoshiro_impl::next();s[1] = xoshiro_impl::next();s[2] = xoshiro_impl::next();s[3] = xoshiro_impl::next();}static constexpr T min(){return std::numeric_limits<T>::min();}static constexpr T max(){return std::numeric_limits<T>::max();}T operator()(){return next();}private:static constexpr T rotl(const T x, int k){return (x << k) | (x >> (32 - k));}T next(){const T ans = rotl(s[1] * 5, 7) * 9;const T t = s[1] << 9;s[2] ^= s[0];s[3] ^= s[1];s[1] ^= s[2];s[0] ^= s[3];s[2] ^= t;s[3] = rotl(s[3], 11);return ans;}T s[4];};class Xoshiro64{public:using result_type = u64;using T = result_type;Xoshiro64(T seed = 0){xoshiro_impl::x = seed;s[0] = xoshiro_impl::next();s[1] = xoshiro_impl::next();s[2] = xoshiro_impl::next();s[3] = xoshiro_impl::next();}static constexpr T min(){return std::numeric_limits<T>::min();}static constexpr T max(){return std::numeric_limits<T>::max();}T operator()(){return next();}private:static constexpr T rotl(const T x, int k){return (x << k) | (x >> (64 - k));}T next(){const T ans = rotl(s[1] * 5, 7) * 9;const T t = s[1] << 17;s[2] ^= s[0];s[3] ^= s[1];s[1] ^= s[2];s[0] ^= s[3];s[2] ^= t;s[3] = rotl(s[3], 45);return ans;}T s[4];};#pragma endregion#pragma region RNGtemplate<typename Rng>class RNG{public:using result_type = typename Rng::result_type;using T = result_type;static constexpr T min(){return Rng::min();}static constexpr T max(){return Rng::max();}RNG() : RNG(std::random_device{}()) {}RNG(T seed) : m_rng(seed) {}T operator()(){return m_rng();}template<typename T>T val(T min, T max){return std::uniform_int_distribution<T>(min, max)(m_rng);}template<typename T>Pair<T, T> pair(T min, T max){return std::minmax({val<T>(min, max), val<T>(min, max)});}template<typename T>Vec<T> vec(int n, T min, T max){return genVec<T>(n, [&]() { return val<T>(min, max); });}template<typename T>Vec<Vec<T>> vvec(int n, int m, T min, T max){return genVec<Vec<T>>(n, [&]() { return vec(m, min, max); });}private:Rng m_rng;};RNG<std::mt19937> rng;RNG<std::mt19937_64> rng64;RNG<Xoshiro32> rng_xo;RNG<Xoshiro64> rng_xo64;#pragma endregion#pragma region Printerclass printer{public:printer(Ostream& os = std::cout) : m_os{os}{m_os << std::fixed << std::setprecision(15);}template<typename... Args>int operator()(const Args&... args){dump(args...);return 0;}template<typename... Args>int ln(const Args&... args){dump(args...), m_os << '\n';return 0;}template<typename... Args>int el(const Args&... args){dump(args...), m_os << std::endl;return 0;}private:template<typename T>void dump(const T& v){m_os << v;}template<typename T>void dump(const Vec<T>& vs){for (const int i : rep(vs.size())) {m_os << (i ? " " : ""), dump(vs[i]);}}template<typename T>void dump(const Vec<Vec<T>>& vss){for (const int i : rep(vss.size())) {m_os << (i ? "" : "\n"), dump(vss[i]);}}template<typename T, typename... Ts>int dump(const T& v, const Ts&... args){dump(v), m_os << ' ', dump(args...);return 0;}Ostream& m_os;};printer out;#pragma endregion#pragma region Scannerclass scanner{public:scanner(Istream& is = std::cin) : m_is{is}{m_is.tie(nullptr)->sync_with_stdio(false);}template<typename T>T val(){T v;return m_is >> v, v;}template<typename T>T val(T offset){return val<T>() - offset;}template<typename T>Vec<T> vec(int n){return genVec<T>(n, [&]() { return val<T>(); });}template<typename T>Vec<T> vec(int n, T offset){return genVec<T>(n, [&]() { return val<T>(offset); });}template<typename T>Vec<Vec<T>> vvec(int n, int m){return genVec<Vec<T>>(n, [&]() { return vec<T>(m); });}template<typename T>Vec<Vec<T>> vvec(int n, int m, const T offset){return genVec<Vec<T>>(n, [&]() { return vec<T>(m, offset); });}template<typename... Args>auto tup(){return Tup<Args...>{val<Args>()...};}template<typename... Args>auto tup(const Args&... offsets){return Tup<Args...>{val<Args>(offsets)...};}private:Istream& m_is;};scanner in;#pragma endregiontemplate<typename T = int>class Graph{public:struct Edge{Edge() = default;Edge(int i, int t, T c) : ind{i}, to{t}, cost{c} {}int ind;int to;T cost;operator int() const{return to;}};Graph(int n) : m_v{n}, m_e{0}, m_edges(n) {}void addEdge(int u, int v, bool bi = false){m_edges[u].emplace_back(m_e, v, 1);if (bi) { m_edges[v].emplace_back(m_e, u, T{1}); }m_e++;}void addEdge(int u, int v, const T& c, bool bi = false){m_edges[u].emplace_back(m_e, v, c);if (bi) { m_edges[v].emplace_back(m_e, u, c); }m_e++;}const Vec<Edge>& operator[](const int u) const{return m_edges[u];}Vec<Edge>& operator[](const int u){return m_edges[u];}int size() const{return m_v;}int v() const{return m_v;}int e() const{return m_e;}friend Ostream& operator<<(Ostream& os, const Graph& g){for (int u : rep(g.m_v)) {for (const auto& [ind, to, cost] : g[u]) {os << "[" << ind << "]: " << u << "->" << to << "(" << cost<< ")\n";}}return os;}Vec<T> depths(int root = 0){const int N = size();Vec<T> ds(N, 0);Fixpoint([&](auto dfs, int u, int p) -> void {for (const auto& e : m_edges[u]) {const int v = e.to;const T c = e.cost;if (v == p) { continue; }ds[v] = ds[u] + c;dfs(v, u);}})(root, -1);return ds;}Vec<int> parents(int root = 0){const int N = size();Vec<int> ps(N, -1);Fixpoint([&](auto dfs, int u, int p) -> void {for (const auto& e : m_edges[u]) {const int v = e.to;const T c = e.cost;if (v == p) { continue; }ps[v] = u;dfs(v, u);}})(root, -1);return ps;}private:int m_v, m_e;Vec<Vec<Edge>> m_edges;};struct modinfo{void set_mod(const u32 nmod) { mod = nmod; }u32 mod, root, max2p;};template<const modinfo& info>class modint{public:static constexpr const u32& mod = info.mod;static constexpr const u32& root = info.root;static constexpr const u32& max2p = info.max2p;constexpr modint() : m_val{0} {}constexpr modint(const i64 v) : m_val{normll(v)} {}constexpr void set_raw(const u32 v) { m_val = v; }constexpr modint operator-() const { return modint{0} - (*this); }constexpr modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; }constexpr modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; }constexpr modint& operator*=(const modint& m) { return m_val = normll((i64)m_val * (i64)m() % (i64)mod), *this; }constexpr modint& operator/=(const modint& m) { return *this *= m.inv(); }constexpr modint operator+(const modint& m) const { return modint{*this} += m; }constexpr modint operator-(const modint& m) const { return modint{*this} -= m; }constexpr modint operator*(const modint& m) const { return modint{*this} *= m; }constexpr modint operator/(const modint& m) const { return modint{*this} /= m; }constexpr bool operator==(const modint& m) const { return m_val == m(); }constexpr bool operator!=(const modint& m) const { return not(*this == m); }friend std::istream& operator>>(std::istream& is, modint& m){i64 v;return is >> v, m = v, is;}friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); }constexpr u32 get() const { return m_val; }constexpr u32 operator()() const { return m_val; }template<typename Int>constexpr modint pow(Int n) const { return power(*this, n); }constexpr modint inv() const { return pow(mod - 2); }static modint sinv(const u32 n){static std::vector<modint> is{1, 1};for (u32 i = (u32)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); }return is[n];}static modint fact(const u32 n){static std::vector<modint> fs{1, 1};for (u32 i = (u32)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); }return fs[n];}static modint ifact(const u32 n){static std::vector<modint> ifs{1, 1};for (u32 i = (u32)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); }return ifs[n];}static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); }private:static constexpr u32 norm(const u32 x) { return x < mod ? x : x - mod; }static constexpr u32 normll(const i64 x) { return norm(u32(x % (i64)mod + (i64)mod)); }u32 m_val;};constexpr modinfo modinfo_1000000007 = {1000000007, 5, 1};constexpr modinfo modinfo_998244353 = {998244353, 3, 23};using modint_1000000007 = modint<modinfo_1000000007>;using modint_998244353 = modint<modinfo_998244353>;#pragma endregionint main(){using mint = modint_998244353;const auto N = in.val<int>();Graph g(N);for (const int i : rep(N - 1)) {const auto [u, v] = in.tup<int, int>(1, 1);g.addEdge(u, v, true);}mint ans = 0;mint bunbo = mint(N) * (N - 1) / 2 * (N - 1);Vec<int> subs(N, 1);Fixpoint([&](auto dfs, int u, int p) -> void {for (const int v : g[u]) {if (v == p) { continue; }dfs(v, u);subs[u] += subs[v];ans += (mint)subs[v] * (subs[v] - 1) / 2+ mint(N - subs[v]) * (N - subs[v] - 1) / 2;}})(0, -1);out.ln(ans / bunbo);return 0;}