結果
問題 |
No.2618 除霊
|
ユーザー |
|
提出日時 | 2024-01-27 03:12:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 633 ms / 2,000 ms |
コード長 | 956 bytes |
コンパイル時間 | 2,078 ms |
コンパイル使用メモリ | 197,900 KB |
最終ジャッジ日時 | 2025-02-19 00:08:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main () { int N; cin >> N; std::vector<int> tr[200020] ; for (int i = 1; i < N; i ++) { int a, b; cin >> a >> b; tr[--a].push_back(--b); tr[b].push_back(a); } vector<int> ex(N, 0); vector<int> ne_h(N, 0); int M; cin >> M; for (int i = 0; i < M; i ++) { int a; cin >> a; ex[--a] = 1; for (auto v : tr[a]) { ne_h[v] = 1; } ne_h[a] = 1; } int sssu = accumulate(ne_h.begin(), ne_h.end(), 0); vector<int> ans(N, sssu), adj(N, 0); for (int i = 0; i < N; i ++) { if (!ne_h[i]) continue; ans[i] --; int fl = -1; for (auto v : tr[i]) { if (ex[v]) { if (fl != -1) { fl = -2; } else { fl = v; } } } if (fl >= 0) { ans[fl] --; if (!ex[i]) { adj[fl] --; ans[i] ++; } } else if (fl == -1) { adj[i] --; } } for (int i = 0; i < N; i ++) { for (auto v : tr[i]) { ans[i] += adj[v]; } cout << ans[i] << endl; } }