結果

問題 No.3189 Semifinal Stage
ユーザー wsrtrt
提出日時 2025-06-21 00:00:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,786 ms / 4,000 ms
コード長 4,605 bytes
コンパイル時間 4,820 ms
コンパイル使用メモリ 313,308 KB
実行使用メモリ 46,552 KB
最終ジャッジ日時 2025-06-21 00:01:33
合計ジャッジ時間 11,576 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto& i:a)
#define ff first 
#define ss second 
#define all(a) begin(a),end(a)
#define allr(a) rbegin(a),rend(a)
#define pb push_back
using ll =long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
template<class T> inline bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<class T> inline bool chmax(T& a,T b){return a<b?a=b,1:0;}

const int INFI=numeric_limits<int>::max()/2;
const ll INFL=numeric_limits<ll>::max()/2;

#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
long long modpow(long long a, long long n, long long mod) {
    a%=mod;
    assert(a!=0||n!=0);
    if(a==0)return 0;
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template <typename T, typename F>
struct SparseTable {
  F f;
  vector<vector<T> > st;
  vector<int> lookup;

  SparseTable() = default;

  explicit SparseTable(const vector<T> &v, const F &f) : f(f) {
    const int n = (int)v.size();
    const int b = 32 - __builtin_clz(n);
    st.assign(b, vector<T>(n));
    for (int i = 0; i < v.size(); i++) {
      st[0][i] = v[i];
    }
    for (int i = 1; i < b; i++) {
      for (int j = 0; j + (1 << i) <= n; j++) {
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for (int i = 2; i < lookup.size(); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  inline T fold(int l, int r) const {
    int b = lookup[r - l];
    return f(st[b][l], st[b][r - (1 << b)]);
  }
};

template <typename T, typename F>
SparseTable<T, F> get_sparse_table(const vector<T> &v, const F &f) {
  return SparseTable<T, F>(v, f);
}
void solve(){
    
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    vector<vector<int>> g(n);
    vi u(n-1),v(n-1);
    rep(i,0,n-1){
        cin>>u[i]>>v[i];
        u[i]--;v[i]--;
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    int M=500;
    int q;cin>>q;
    vector<pii> query(q);
    rep(i,0,q){
        int t,u;cin>>t>>u;u--;
        query[i]={t,u};
    }
    vector<pii> ett(2*n);
    vector<int> in(n),out(n),depth(n);
    auto dfs=[&,time{0}](auto&& self,int pos,int d=0,int pre=-1)mutable ->void {
        in[pos]=time;
        ett[time]={d,pos};
        depth[pos]=d;
        fore(i,g[pos]){
            if(i==pre)continue;
            time++;
            self(self,i,d+1,pos);
            time++;
            ett[time]={d,pos};
        }
        out[pos]=time+1;
    };
    dfs(dfs,0);
    auto st=get_sparse_table(ett,[](pii a,pii b){return min(a,b);});
    auto lca=[&](int u,int v){
        return st.fold(min(in[u],in[v]),max(out[u],out[v])).ss;
    };
    auto dist=[&](int u,int v){
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    };
    vi c(n);
    vi dp(n);
    vi flag(n);
    vi ver;//いい感じにやる頂点
    //全方位木DP
    auto dfs2=[&](auto&& self,int pos,int pre=-1)->int {
        if(c[pos]==1&&flag[pos]==0){
            dp[pos]=0;
        }
        fore(i,g[pos]){
            if(i==pre)continue;
            chmin(dp[pos],self(self,i,pos)+1);
        }
        return dp[pos];
    };
    auto dfs3=[&](auto&& self,int pos,int pre=-1)->void {
        fore(i,g[pos]){
            if(i==pre)continue;
            chmin(dp[i],dp[pos]+1);
            self(self,i,pos);
        }
    };
    for(int i=0;i<q;i+=M){
        //初期化
        dp.assign(n,INFI);
        flag.assign(n,0);
        ver.clear();
        rep(j,i,min(i+M,q)){
            if(query[j].ff==1){
                flag[query[j].ss]=1;
            }
        }
        rep(j,0,n){
            if(flag[j]){
                ver.pb(j);
            }
        }
        dfs2(dfs2,0);
        dfs3(dfs3,0);
        //クエリ処理
        rep(j,i,min(i+M,q)){
            int t,u;tie(t,u)=query[j];
            if(t==1){
                c[u]^=1;
            }
            else{
                int ans{dp[u]};
                if(c[u]==1){
                    ans=0;
                }
                fore(k,ver){
                    if(c[k]==1){
                        chmin(ans,dist(u,k));
                    }
                }
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}
/*

*/
0