結果
問題 | No.1718 Random Squirrel |
ユーザー |
![]() |
提出日時 | 2021-10-22 23:27:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 3,337 bytes |
コンパイル時間 | 4,663 ms |
コンパイル使用メモリ | 257,728 KB |
最終ジャッジ日時 | 2025-01-25 04:24:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; template<class S, class E> struct Rerooting { const vector<vector<E>>& g; const int n; const int root; vector<vector<S>> dp, sl, sr; Rerooting(const vector<vector<E>>& g, int root=0): g(g), n(g.size()), root(root), dp(n), sl(n), sr(n) { dfs1(root); dfs2(root); } S dfs1(int u, int p=-1) { const int sz = g[u].size(); dp[u].resize(sz); sl[u].resize(sz + 1); sr[u].resize(sz + 1); S res; for(int i = 0; i < sz; i++) { const E& e = g[u][i]; int v = dest(e); if (v == p) continue; if constexpr (is_same_v<E, int>) dp[u][i] = dfs1(v, u); else dp[u][i] = dfs1(v, u).apply(e); res = res.merge(dp[u][i]); } return res.add_parent(u); } void dfs2(int u, int p=-1) { const int sz = g[u].size(); { S s; for(int i = 0; i < sz; i++) { s = s.merge(dp[u][i]); sl[u][i + 1] = s; } } { S s; for(int i = sz - 1; i >= 0; i--) { s = s.merge(dp[u][i]); sr[u][i] = s; } } for(int i = 0; i < sz; i++) { int v = dest(g[u][i]); if (v == p) continue; const int sz_v = g[v].size(); for(int j = 0; j < sz_v; j++) { const E& e = g[v][j]; int w = dest(e); if (w != u) continue; if constexpr (is_same_v<E, int>) dp[v][j] = sl[u][i].merge(sr[u][i + 1]).add_parent(u); else dp[v][j] = sl[u][i].merge(sr[u][i + 1]).add_parent(u).apply(e); break; } dfs2(v, u); } } S get_res(int v) { return sr[v][0].add_parent(v); } private: int dest(const E& e) { if constexpr (is_same<E, int>::value) return e; else return e.to; }; }; vector<char> d; struct S { int v1 = 0, v2 = 0; bool exist = false; S add_parent(int v) { if (!exist && !d[v]) return S{}; return S{v1 + 1, v2 + 2, true}; } S merge(const S& rhs) { if (!exist) return rhs; if (!rhs.exist) return *this; return S{min(v1 + rhs.v2, v2 + rhs.v1), v2 + rhs.v2, true}; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; VVI to(n); rep(i, n - 1) { int u, v; cin >> u >> v; u--, v--; to[u].push_back(v); to[v].push_back(u); } d.resize(n, false); rep(i, k) { int di; cin >> di; d[di - 1] = true; } Rerooting<S, int> rt(to); rep(i, n) { cout << rt.sr[i][0].v1 << '\n'; } }