結果
問題 | No.2116 Making Forest Hard |
ユーザー | Jaehyun Koo |
提出日時 | 2023-04-28 22:44:45 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 222 ms / 8,000 ms |
コード長 | 4,805 bytes |
コンパイル時間 | 3,043 ms |
コンパイル使用メモリ | 228,688 KB |
実行使用メモリ | 27,820 KB |
最終ジャッジ日時 | 2024-04-29 00:09:10 |
合計ジャッジ時間 | 11,685 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
10,368 KB |
testcase_01 | AC | 8 ms
10,368 KB |
testcase_02 | AC | 137 ms
14,720 KB |
testcase_03 | AC | 132 ms
14,464 KB |
testcase_04 | AC | 140 ms
21,156 KB |
testcase_05 | AC | 202 ms
23,724 KB |
testcase_06 | AC | 161 ms
25,872 KB |
testcase_07 | AC | 170 ms
25,144 KB |
testcase_08 | AC | 104 ms
23,776 KB |
testcase_09 | AC | 118 ms
25,496 KB |
testcase_10 | AC | 25 ms
11,648 KB |
testcase_11 | AC | 182 ms
23,552 KB |
testcase_12 | AC | 142 ms
25,372 KB |
testcase_13 | AC | 207 ms
23,328 KB |
testcase_14 | AC | 191 ms
14,720 KB |
testcase_15 | AC | 10 ms
10,496 KB |
testcase_16 | AC | 147 ms
27,820 KB |
testcase_17 | AC | 134 ms
13,440 KB |
testcase_18 | AC | 114 ms
13,952 KB |
testcase_19 | AC | 61 ms
17,788 KB |
testcase_20 | AC | 76 ms
16,168 KB |
testcase_21 | AC | 86 ms
12,544 KB |
testcase_22 | AC | 157 ms
19,648 KB |
testcase_23 | AC | 26 ms
12,364 KB |
testcase_24 | AC | 25 ms
11,136 KB |
testcase_25 | AC | 110 ms
18,208 KB |
testcase_26 | AC | 145 ms
27,692 KB |
testcase_27 | AC | 36 ms
11,392 KB |
testcase_28 | AC | 94 ms
13,312 KB |
testcase_29 | AC | 180 ms
20,808 KB |
testcase_30 | AC | 111 ms
13,824 KB |
testcase_31 | AC | 65 ms
13,844 KB |
testcase_32 | AC | 194 ms
22,056 KB |
testcase_33 | AC | 12 ms
10,624 KB |
testcase_34 | AC | 47 ms
14,720 KB |
testcase_35 | AC | 191 ms
21,196 KB |
testcase_36 | AC | 100 ms
23,928 KB |
testcase_37 | AC | 20 ms
11,520 KB |
testcase_38 | AC | 154 ms
27,416 KB |
testcase_39 | AC | 212 ms
25,516 KB |
testcase_40 | AC | 60 ms
13,952 KB |
testcase_41 | AC | 140 ms
18,564 KB |
testcase_42 | AC | 118 ms
14,208 KB |
testcase_43 | AC | 140 ms
14,848 KB |
testcase_44 | AC | 201 ms
25,152 KB |
testcase_45 | AC | 94 ms
15,936 KB |
testcase_46 | AC | 137 ms
14,796 KB |
testcase_47 | AC | 52 ms
13,568 KB |
testcase_48 | AC | 51 ms
13,372 KB |
testcase_49 | AC | 8 ms
10,368 KB |
testcase_50 | AC | 222 ms
23,312 KB |
testcase_51 | AC | 190 ms
23,340 KB |
testcase_52 | AC | 180 ms
22,316 KB |
testcase_53 | AC | 202 ms
23,848 KB |
testcase_54 | AC | 202 ms
14,848 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; using pi = array<lint, 2>; #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() const int MAXN = 300005; const int mod = 998244353; const int inv2 = (mod + 1) / 2; // test weak... no line struct mint { int val; mint() { val = 0; } mint(const lint &v) { val = (-mod <= v && v < mod) ? v : v % mod; if (val < 0) val += mod; } friend ostream &operator<<(ostream &os, const mint &a) { return os << a.val; } friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; } friend bool operator!=(const mint &a, const mint &b) { return !(a == b); } friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; } mint operator-() const { return mint(-val); } mint &operator+=(const mint &m) { if ((val += m.val) >= mod) val -= mod; return *this; } mint &operator-=(const mint &m) { if ((val -= m.val) < 0) val += mod; return *this; } mint &operator*=(const mint &m) { val = (lint)val * m.val % mod; return *this; } friend mint ipow(mint a, lint p) { mint ans = 1; for (; p; p /= 2, a *= a) if (p & 1) ans *= a; return ans; } mint inv() const { return ipow(*this, mod - 2); } mint &operator/=(const mint &m) { return (*this) *= m.inv(); } friend mint operator+(mint a, const mint &b) { return a += b; } friend mint operator-(mint a, const mint &b) { return a -= b; } friend mint operator*(mint a, const mint &b) { return a *= b; } friend mint operator/(mint a, const mint &b) { return a /= b; } operator int64_t() const { return val; } }; mint ret = 0; struct node { int j; mint A, S; bool operator<(const node &nd) const { return j < nd.j; } }; vector<int> gph[MAXN]; int val[MAXN], sz[MAXN], n; vector<node> merge(vector<node> a, vector<node> b) { vector<int> bisect(sz(a) + 1); int j = 0; for (int i = 0; i < sz(a); i++) { while (j < sz(b) && b[j].j < a[i].j) j++; bisect[i] = j; } bisect[sz(a)] = sz(b); mint tasum = 0, tssum = 0; mint asum = 0, ssum = 0; vector<node> c; for (int i = 0; i < sz(a); i++) { for (int j = (i ? bisect[i - 1] : 0); j < bisect[i]; j++) { asum += b[j].A; ssum += b[j].S; } tasum += a[i].A; tssum += a[i].S; a[i].A = a[i].A * ssum + a[i].S * asum; a[i].S = a[i].S * ssum; for (int j = bisect[i]; j < bisect[i + 1]; j++) { auto cp = b[j]; cp.A = (tssum)*cp.A + tasum * cp.S; cp.S = (tssum)*cp.S; c.push_back(cp); } } vector<node> nxt(sz(a) + sz(c)); merge(all(a), all(c), nxt.begin()); vector<node> z; for (int i = 0; i < sz(nxt);) { int j = i; node toput; toput.j = nxt[i].j; while (j < sz(nxt) && nxt[i].j == nxt[j].j) { toput.A += nxt[j].A; toput.S += nxt[j].S; j++; } i = j; z.push_back(toput); } return z; } void pdfs(int x) { sz[x] = 1; for (auto &y : gph[x]) { gph[y].erase(find(all(gph[y]), x)); pdfs(y); sz[x] += sz[y]; } sort(all(gph[x]), [&](const int &p, const int &q) { return sz[p] > sz[q]; }); } auto cmp = [](vector<node> &a, vector<node> &b) { return sz(a) > sz(b); }; vector<node> dnc(int s, int e, vector<vector<node>> &h) { if (s == e) return h[s]; int m = (s + e) / 2; return merge(dnc(s, m, h), dnc(m + 1, e, h)); } vector<node> solve(int x) { vector<int> hchn; for (int i = x;; i = gph[i][0]) { hchn.push_back(i); if (sz(gph[i]) == 0) break; } vector<vector<node>> heap; priority_queue<vector<node>, vector<vector<node>>, decltype(cmp)> pq(cmp); // max heap for (int i = 0; i < sz(hchn); i++) { int x = hchn[i]; vector<node> a; a.push_back((node){val[x], mint(1), mint(1)}); pq.push(a); for (int j = 1; j < sz(gph[x]); j++) { int y = gph[x][j]; auto b = solve(y); for (auto &bb : b) { ret += mint(bb.j) * bb.A * mint((mod + 1) / 2); bb.A *= mint(inv2); bb.S *= mint(inv2); } b.push_back({val[x], mint(0), mint(inv2)}); sort(all(b)); pq.push(b); } while (sz(pq) > 1) { auto x = pq.top(); pq.pop(); auto y = pq.top(); pq.pop(); pq.push(merge(x, y)); } heap.push_back(pq.top()); pq.pop(); } auto cur = heap.back(); for (int i = sz(heap) - 2; i >= 0; i--) { for (auto &bb : cur) { ret += mint(bb.j) * bb.A * mint((mod + 1) / 2); bb.A *= mint(inv2); bb.S *= mint(inv2); } cur.push_back({val[hchn[i]], mint(0), mint(inv2)}); sort(all(cur)); cur = merge(heap[i], cur); } return cur; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i++) { cin >> val[i]; } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; gph[u].push_back(v); gph[v].push_back(u); } pdfs(0); auto ans = solve(0); for (auto &z : ans) { ret += z.A * mint(z.j); } cout << ret * ipow(mint(2), n - 1) << "\n"; }