結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
|
提出日時 | 2025-08-01 22:55:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 1,325 bytes |
コンパイル時間 | 2,126 ms |
コンパイル使用メモリ | 214,092 KB |
実行使用メモリ | 18,832 KB |
最終ジャッジ日時 | 2025-08-01 22:55:28 |
合計ジャッジ時間 | 6,066 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n); for(auto &&v : a) cin >> v; vector<set<int>> g(n); for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; u--, v--; g[u].insert(v); g[v].insert(u); } vector<int> dp(n, 1 << 30); queue<int> que; for(int i = 0; i < m; i++){ int v; cin >> v; v--; dp[v] = 0; que.emplace(v); } while(!que.empty()){ int v = que.front(); que.pop(); for(auto u : g[v]){ if(dp[v] + 1 >= dp[u]) continue; dp[u] = dp[v] + 1; que.emplace(u); } } priority_queue<pair<int,int>> pq; for(int v = 0; v < n; v++){ if(g[v].size() == 1){ pq.emplace(a[v], v); } } ll ans = 0; for(int t = 0; !pq.empty(); ){ auto [p, v] = pq.top(); pq.pop(); if(t >= dp[v]) continue; ans += p; if(!g[v].empty()){ int pr = *g[v].begin(); g[pr].erase(v); if(g[pr].size() <= 1){ pq.emplace(a[pr], pr); } } t++; } cout << ans << '\n'; }