結果
問題 | No.1718 Random Squirrel |
ユーザー |
![]() |
提出日時 | 2022-04-30 11:18:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 316 ms / 2,000 ms |
コード長 | 4,223 bytes |
コンパイル時間 | 1,875 ms |
コンパイル使用メモリ | 127,192 KB |
最終ジャッジ日時 | 2025-01-29 00:49:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;#include <vector>using namespace std;struct S {int sum_children;ll come_back, not_come_back;S(int sum_children, ll come_back, ll not_come_back): sum_children(sum_children), come_back(come_back), not_come_back(not_come_back) {}};S e(){return S(0, 0, 0);}S f(S dp, int v){return dp;};bool is_drink[100000];S g(S dp, int v){if(is_drink[v]){return S(dp.sum_children+1, dp.come_back, dp.not_come_back);}return dp;};S merge(S a, S b){if(b.sum_children == 0) return a;ll come_back = a.come_back+b.come_back+2;ll not_come_back = min(a.come_back+b.not_come_back+1, a.not_come_back+b.come_back+2);return S(a.sum_children+b.sum_children, come_back, not_come_back);};S merge2(S a, S b){if(b.sum_children == 0) return a;ll come_back = a.come_back+b.come_back;ll not_come_back = min(a.come_back+b.not_come_back, a.not_come_back+b.come_back);return S(a.sum_children+b.sum_children, come_back, not_come_back);};template<typename T>struct ReRooting {int n;T(*e)();T(*merge)(T, T);T(*f)(T, int);T(*g)(T, int);vector<vector<int>> G;vector<vector<T>> dp;ReRooting(int n, T(*e)(), T(*merge)(T, T), T(*f)(T, int), T(*g)(T, int)): n(n), e(e), merge(merge), f(f), g(g) {dp.resize(n);G.resize(n);}ReRooting(vector<vector<int>> G, T(*e)(), T(*merge)(T, T), T(*f)(T, int), T(*g)(T, int)): n(G.size()), G(G), e(e), merge(merge), f(f), g(g) {dp.resize(n);}void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}T dfs1(int v, int p){T ans = e();for(int i = 0; i < G[v].size(); i++){int u = G[v][i];if(u == p) continue;dp[v][i] = dfs1(u, v);ans = merge(ans, dp[v][i]);}return g(ans, v);}void dfs2(int v, int p, T from_par){int deg = G[v].size();for(int i = 0; i < deg; i++){if(G[v][i] == p){dp[v][i] = from_par;break;}}vector<T> from_right(deg+1, e());for(int i = deg-1; i >= 0; i--){from_right[i] = merge(from_right[i+1], f(dp[v][i], G[v][i]));}T from_left = e();for(int i = 0; i < deg; i++){int u = G[v][i];if(u != p){T x = merge2(from_left, from_right[i+1]);dfs2(u, v, g(x, v));}from_left = merge(from_left, f(dp[v][i], G[v][i]));}}vector<T> solve(int r = 0){for(int i = 0; i < n; i++) dp[i].assign(G[i].size(), e());dfs1(r, -1);dfs2(r, -1, e());vector<T> ans(n, e());for(int v = 0; v < n; v++){for(int i = 0; i < G[v].size(); i++){ans[v] = merge(ans[v], f(dp[v][i], G[v][i]));}ans[v] = g(ans[v], v);}return ans;}};int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int n, k; cin >> n >> k;vector<vector<int>> G(n);for(int i = 0; i < n-1; i++){int u, v; cin >> u >> v; u--; v--;G[u].push_back(v);G[v].push_back(u);}vector<int> d(k);for(int i = 0; i < k; i++) {cin >> d[i];d[i]--;is_drink[d[i]] = true;}ReRooting<S> rr(G, e, merge, f, g);auto ans = rr.solve();for(int i = 0; i < n; i++){cout << ans[i].not_come_back << endl;}}