結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 1000000000
template <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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0