結果

問題 No.3189 Semifinal Stage
ユーザー GOTKAKO
提出日時 2025-06-20 23:15:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 394 ms / 4,000 ms
コード長 8,710 bytes
コンパイル時間 3,145 ms
コンパイル使用メモリ 247,512 KB
実行使用メモリ 44,400 KB
最終ジャッジ日時 2025-06-20 23:16:13
合計ジャッジ時間 11,669 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class CD{ //Centroid-Decomposition
    public:
    int n = 0; long long suma = 0;
    vector<int> A,par,cent;
    vector<long long> siz;
    vector<bool> already;
    vector<vector<int>> Graph;
 
    void make(vector<vector<int>> &G,vector<int> B = {}){ //Bは頂点重み.
        n = G.size(); Graph = G;
        if(B.size()){A = B; for(auto &b : B) suma += b;}
        else A.resize(n,1),suma = n; 
        siz.resize(n); par.resize(n); already.resize(n);
    }
 
    void findcentroid(int pos,int back,long long all){ //重心重み考慮.
        par.at(pos) = back; siz.at(pos) = A.at(pos);
        bool centroid = true;
        for(auto to : Graph.at(pos)){
            if(to == back || already.at(to)) continue;
            findcentroid(to,pos,all);
            if(siz.at(to) > all/2) centroid = false;
            siz.at(pos) += siz.at(to);
        }
        if(all-siz.at(pos) > all/2) centroid = false;
        if(centroid) cent.push_back(pos);
    }
    void findcentroid2(int pos,int back,long long all){ //重心重み1.
        par.at(pos) = back; siz.at(pos) = 1;
        bool centroid = true;
        for(auto to : Graph.at(pos)){
            if(to == back || already.at(to)) continue;
            findcentroid2(to,pos,all);
            if(siz.at(to) > all/2) centroid = false;
            siz.at(pos) += siz.at(to);
        }
        if(all-siz.at(pos) > all/2) centroid = false;
        if(centroid) cent.push_back(pos);
    }
    pair<int,vector<vector<int>>> arrange(){ //メイン.
        int retroot = -1;
        vector<vector<int>> ret(n);
        queue<tuple<int,long long,int>> Q;
        Q.push({0,n,-1});
        while(Q.size()){
            auto[root,all,p] = Q.front(); Q.pop();
            cent.clear();
            findcentroid2(root,-1,all);
            int c = cent.at(0);
            already.at(c) = true;
            if(retroot == -1) retroot = c;
            if(p != -1) ret.at(p).push_back(c);
            for(auto to : Graph.at(c)){
                if(already.at(to)) continue;
                if(to == par.at(c)) Q.push({to,all-siz.at(c),c});
                else Q.push({to,siz.at(to),c});
            }
        }
        return {retroot,ret};
    }
    vector<int> FindCentall(){ //1回重心求めるだけ
        cent.clear();
        findcentroid(0,-1,suma);
        return cent;
    }
    int FindCentone(){vector<int> R = FindCentall(); return R.at(0);}
};

class SpecialSparseTable{ //LCA専用.
    private:
    int log = 0;
    pair<int,int> op(pair<int,int> &a,pair<int,int> &b){return min(a,b);}
    pair<int,int> add(pair<int,int> &a,pair<int,int> &b){return {a.first+b.first,a.second+b.second};}
    vector<int> check,belong,Second;
    vector<pair<int,int>> Add;
    vector<vector<vector<pair<int,int>>>> Group;
    vector<vector<pair<int,int>>> table;
    void maketable(vector<pair<int,int>> &A){
        int n = A.size();
        table.resize(n+1); check.resize(n+1);
        int p2 = 1;
        for(int i=1; i<=n; i++){
            if(i == p2) check.at(i) = i,p2 *= 2;
            else check.at(i) = check.at(i-1);
        }
        table.at(1) = A;
        for(int i=2; i<=n; i*=2){
            table.at(i).resize(n);
            for(int k=0; k<=n-i; k++) table[i][k] = op(table[i>>1][k],table[i>>1][k+(i>>1)]);
        }
    }
    void makeGroup(vector<pair<int,int>> &A){
        int loop = 1<<(log-1);
        Group.resize(loop,vector<vector<pair<int,int>>>(log,vector<pair<int,int>>(log)));
        for(int i=0; i<loop; i++){
            vector<int> now(1);
            for(int k=0; k<log-1; k++){
                if(i&(1<<k)) now.push_back(now.back()+1);
                else now.push_back(now.back()-1);
            }
            for(int l=0; l<log; l++){
                int mina = 1001001001,pos = -1;
                for(int r=l; r<log; r++){
                    if(mina > now.at(r)) mina = now.at(r),pos = r;
                    Group.at(i).at(l).at(r) = {mina,pos};
                }
            }
        }
    }
    pair<int,int> tablerange(int l,int r){//[L,R)だよ.
        int len = r-l,pos = check.at(len);
        return op(table.at(pos).at(l),table.at(pos).at(r-pos));
    }
    public:
    void make(vector<pair<int,int>> &A){
        int p2 = 1,n = A.size();
        while(p2 < n) p2 *= 2,log++;
        log = max(1,(log+1)/2);
 
        vector<pair<int,int>> sepa;
        for(int i=0; i<n; i+=log){
            int r = min(n,i+log),g = 0;
            pair<int,int> now = {1001001001,-1};
            for(int k=i; k<r; k++){
                if(k != r-1 && A.at(k).first+1 == A.at(k+1).first) g += (1<<(k-i));
                Second.push_back(A.at(k).second);
                if(now > A.at(k)) now = {A.at(k).first,k};
            }
            Add.push_back({A.at(i).first,i});
            sepa.push_back(now); belong.push_back(g);
        }
        maketable(sepa); makeGroup(A); 
    }
    int rangeans(int l,int r){ //[l,r)!
        int l2 = (l+log-1)/log,r2 = r/log;
        pair<int,int> mind = {1001001001,-1};
        if(l2 > r2) mind = add(Group[belong[r2]][l%log][(r-1)%log],Add[r2]);
        else{
            if(l2 < r2) mind = tablerange(l2,r2);
            if(l%log) mind = min(mind,add(Group[belong[l2-1]][l%log][log-1],Add[l2-1]));
            if(r%log) mind = min(mind,add(Group[belong[r2]][0][(r-1)%log],Add[r2]));
        }
        return Second.at(mind.second);
    }
};
class LCA{
    private:
    vector<int> dist,in,out;
    SpecialSparseTable ST;
    public:
    void make1(vector<int> &P){// p0=-1でp1以降だけ
        int r = 0;
        vector<vector<int>> G(P.size()+1);
        for(int i=0; i<P.size(); i++) G.at(P.at(i)).push_back(i+1); 
        make3(G,r);
    }
    void make2(vector<int> &P){//pi=-1 iは固定されていない.
        int r = -1;
        vector<vector<int>> G(P.size());
        for(int i=0; i<P.size(); i++){
            if(P.at(i) == -1) r = i;
            else G.at(P.at(i)).push_back(i);
        }
        make3(G,r);
    }
    void make3(vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,n = Graph.size(),pos = root;
        dist.resize(n),in.resize(n),out.resize(n);
 
        vector<pair<int,int>> depth;
        vector<int> Itr(n,-1),P(n,-1);
        while(pos != -1){
            depth.push_back({dep,pos});
            if(++Itr.at(pos) == 0) in.at(pos) = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
            else{
                to = Graph.at(pos).at(Itr.at(pos));
                if(to == P.at(pos)){
                    Itr.at(pos)++;
                    if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist.at(to) = dist.at(pos)+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int lca(int u,int v){
        int tu = in.at(u),tv = in.at(v);
        if(tu > tv) swap(tu,tv);
        return ST.rangeans(tu,tv+1);
    }
    int twodist(int u,int v){return dist.at(u)+dist.at(v)-2*dist.at(lca(u,v));}
    int onedist(int u){return dist.at(u);} 
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<vector<int>> Graph(N);
    for(int i=0; i<N-1; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    LCA L; L.make3(Graph,0);
    CD Z; Z.make(Graph);
    auto [root,Graph2] = Z.arrange();

    vector<int> par(N);
    auto dfs = [&](auto dfs,int pos,int back) -> void {
        par.at(pos) = back;
        for(auto to : Graph2.at(pos)) dfs(dfs,to,pos);
    };
    dfs(dfs,root,-1);

    int Q; cin >> Q;
    vector<bool> Black(N);
    vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>> Qs(N);
    while(Q--){
        int t,v; cin >> t >> v; v--;
        if(t == 1){
            if(Black.at(v)) Black.at(v) = false;
            else{
                Black.at(v) = true;
                int pos = v;
                while(pos != -1) Qs.at(pos).push({L.twodist(v,pos),v}),pos = par.at(pos);
            }
        }
        else{
            int pos = v,answer = 1001001001;
            while(pos != -1){
                while(Qs.at(pos).size()){
                    auto [d,p] = Qs.at(pos).top();
                    if(Black.at(p) == false) Qs.at(pos).pop();
                    else{answer = min(answer,L.twodist(v,p)); break;}
                }
                pos = par.at(pos);
            }
            cout << answer << "\n";
        }
    }
}
0