結果
問題 | No.1718 Random Squirrel |
ユーザー |
![]() |
提出日時 | 2021-10-22 22:54:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 399 ms / 2,000 ms |
コード長 | 2,615 bytes |
コンパイル時間 | 5,349 ms |
コンパイル使用メモリ | 260,312 KB |
最終ジャッジ日時 | 2025-01-25 04:05:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000template <class Ss, Ss (*op0)(Ss, Ss), Ss (*e)(), class Sv, Ss (*op1)(Sv, Ss), class Se, Ss (*op2)(Se, Ss)>struct rerooting{int n;vector<vector<int>> to;vector<vector<Se>> edge;vector<Ss> subtree,answer;vector<Sv> vertex;rerooting(int _n){n = _n;to.resize(n);edge.resize(n);subtree.resize(n,e());answer.resize(n,e());vertex.resize(n);}rerooting(vector<Sv> v){n = v.size();to.resize(n);edge.resize(n);subtree.resize(n,e());answer.resize(n,e());vertex = v;}void add_directed_edge(int u,int v,Se x){to[u].push_back(v);edge[u].push_back(x);}void add_edge(int u,int v,Se x){add_directed_edge(u,v,x);add_directed_edge(v,u,x);}void solve(){dfs(0,-1);redfs(0,-1,e());}void dfs(int cur,int par){Ss temp = e();for(int i=0;i<to[cur].size();i++){int nxt = to[cur][i];if(nxt==par)continue;dfs(nxt,cur);temp = op0(temp, op2(edge[cur][i], subtree[nxt]));}subtree[cur] = op1(vertex[cur], temp);}void redfs(int cur, int par, Ss ps){vector<Ss> P(to[cur].size()+1,e());rep(i,to[cur].size()){int nxt = to[cur][i];if(nxt!=par)P[i+1] = op2(edge[cur][i], subtree[nxt]);else P[i+1] = op2(edge[cur][i], ps);}vector<Ss> S(P.rbegin(),P.rend()-1);S.insert(S.begin(),e());rep(i,to[cur].size()){P[i+1] = op0(P[i], P[i+1]);S[i+1] = op0(S[i+1], S[i]);}answer[cur] = op1(vertex[cur], P.back());for(int i=0;i<to[cur].size();i++){int nxt = to[cur][i];if(nxt!=par){redfs(nxt,cur,op1(vertex[cur], op0(P[i],S[to[cur].size()-1-i])));}}}};struct subtree{int Cost = 0,Maxi = -Inf;bool f = false;};subtree op0(subtree a,subtree b){a.Maxi = max(a.Maxi,b.Maxi);if(b.f)a.f = true;a.Cost += b.Cost;return a;}subtree e(){return subtree();}subtree op1(int a,subtree b){if(a){b.f = true;b.Maxi = max(b.Maxi,0);}return b;}subtree op2(int a,subtree b){if(b.f){b.Cost += 2;b.Maxi ++;}return b;}int main(){int N,K;cin>>N>>K;vector<int> u(N-1),v(N-1);rep(i,N-1){cin>>u[i]>>v[i];u[i]--;v[i]--;}vector<int> V(N,0);rep(i,K){int x;cin>>x;V[x-1] = 1;}rerooting<subtree,op0,e,int,op1,int,op2> R(V);rep(i,N-1){R.add_edge(u[i],v[i],1);}R.solve();rep(i,N){int ans = R.answer[i].Cost - R.answer[i].Maxi;cout<<ans<<endl;}return 0;}