結果

問題 No.3222 Let the World Forget Me
ユーザー tau1235
提出日時 2025-08-02 07:21:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 1,126 bytes
コンパイル時間 3,813 ms
コンパイル使用メモリ 291,620 KB
実行使用メモリ 11,044 KB
最終ジャッジ日時 2025-08-02 07:21:57
合計ジャッジ時間 9,254 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

int main(){
  using ll=long long;
  ll inf=1e18;
  int n,m;
  cin>>n>>m;
  vector<int> p(n);
  for (int i=0;i<n;i++) cin>>p[i];
  vector<vector<int>> g(n);
  vector<int> d(n);
  vector<bool> visited(n);
  for (int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
    d[a]++;
    d[b]++;
  }
  queue<int> q,nextq;
  for (int i=0;i<m;i++){
    int c;
    cin>>c;
    c--;
    visited[c]=true;
    for (int v:g[c]) q.push(v);
  }
  ll ans=0;
  priority_queue<pair<ll,int>> pq;
  for (int i=0;i<n;i++) if (d[i]==1) pq.push({p[i],i});
  while (!pq.empty()){
    auto [val,v]=pq.top();
    pq.pop();
    if (visited[v]) continue;
    ans+=val;
    for (int u:g[v]){
      if (visited[u]) continue;
      d[u]--;
      if (d[u]==1) pq.push({p[u],u});
    }
    visited[v]=true;
    while (!q.empty()){
      int v=q.front();
      q.pop();
      if (visited[v]) continue;
      visited[v]=true;
      for (int u:g[v]){
        if (visited[u]) continue;
        nextq.push(u);
      }
    }
    swap(q,nextq);
  }
  cout<<ans<<endl;
}
0