結果
問題 | No.2115 Making Forest Easy |
ユーザー |
👑 |
提出日時 | 2022-10-28 23:43:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,559 bytes |
コンパイル時間 | 5,065 ms |
コンパイル使用メモリ | 292,996 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-12 03:14:14 |
合計ジャッジ時間 | 34,024 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 49 TLE * 1 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#include<atcoder/modint>using namespace std;using namespace atcoder;using mint = modint998244353;void solve(){int n;cin >> n;vector<pair<long long, int>> A(n);long long a;for(int i = 0; i < n; i++){cin >> a;A[i] = {a, i};}vector<vector<int>> edges(n, vector<int>());int u, v;for(int i = 0; i < n - 1; i++){cin >> u >> v;u--; v--;edges[u].push_back(v);edges[v].push_back(u);}sort(A.begin(), A.end(), greater<pair<long long, int>>());vector<bool> used(n, false);vector<mint> pow2(n + 1, 1);for(int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2;mint ans = 0;for(auto tmp:A){a = tmp.first;int i = tmp.second;vector<int> dist(n, -1);vector<int> size(n, 0);dist[i] = 0;stack<int> st;st.push(~i);st.push(i);while(!st.empty()){int pos = st.top();st.pop();if(pos >= 0){for(auto npos: edges[pos]){if(dist[npos] == -1){dist[npos] = dist[pos] + 1;st.push(~npos);st.push(npos);}}}else{pos = ~pos;size[pos]++;for(auto npos: edges[pos]) size[pos] += size[npos];}}vector<mint> dp(n, 0);auto dfs=[&](auto self, int pos, int bpos) -> void {dp[pos] = 1;for(auto npos: edges[pos]){if(npos == bpos) continue;if(used[npos]){dp[pos] *= pow2[size[npos] - 1];}else{self(self, npos, pos);dp[pos] *= dp[npos] + pow2[size[npos] - 1];}}};dfs(dfs, i, -1);mint tot = 0;auto dfs2=[&](auto self, int pos, int bpos) -> void {int le = edges[pos].size();vector<mint> L(le + 1, 1);for(int ii = 0; ii < le; ii++){int npos = edges[pos][ii];if(used[npos]) L[ii + 1] = (L[ii] * pow2[size[npos] - 1]);else if(npos == bpos) L[ii + 1] = (L[ii] * dp[npos]);else L[ii + 1] = (L[ii] * (pow2[size[npos] - 1] + dp[npos]));}tot += L[le];vector<mint> R(le + 1, 1);for(int ii = edges[pos].size() - 1; ii >= 0; ii--){int npos = edges[pos][ii];if(used[npos]) R[ii] = (R[ii + 1] * pow2[size[npos] - 1]);else if(npos == bpos) R[ii] = (R[ii + 1] * dp[npos]);else R[ii] = (R[ii + 1] * (pow2[size[npos] - 1] + dp[npos]));}for(int ii = 0; ii < edges[pos].size(); ii++){int npos = edges[pos][ii];if((npos == bpos) || used[npos]) continue;dp[pos] = L[ii] * R[ii + 1];size[pos] = n - size[npos];self(self, npos, pos);}};dfs2(dfs2, i, -1);ans += tot * a;used[i] = true;}cout << ans.val() << "\n";}int main(){cin.tie(0)->sync_with_stdio(0);int t;t = 1;// cin >> t;while(t--) solve();}