結果

問題 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