結果

問題 No.3189 Semifinal Stage
ユーザー wsrtrt
提出日時 2025-06-20 23:46:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,955 bytes
コンパイル時間 6,012 ms
コンパイル使用メモリ 334,980 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 23:47:06
合計ジャッジ時間 13,143 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
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<class T,class F>
struct DisjointSparseTable{
    T ti;F f;
    int sz;int height;
    vector<vector<T>> data;
    vector<T> v;
    int msb(int x){return x==0?-1:31-__builtin_clz(x);}
    void build(){
        for(int i=0;i<height;i++){
            int len=(1<<(height-i-1));
            for(int piv=len;piv<sz;piv+=(len<<1)){
                data[i][piv-1]=v[piv-1];
                data[i][piv]=v[piv];
                for(int j=1;j<len;j++){
                    data[i][piv-1-j]=f(v[piv-1-j],data[i][piv-j]);
                    data[i][piv+j]=f(data[i][piv+j-1],v[piv+j]);
                }
            }
        }
    }
    DisjointSparseTable(vector<T> v,F f,T ti):v(v),f(f),ti(ti){
        int n=v.size();
        sz=1;height=0;
        while(sz<n)sz<<=1,height++;
        data.resize(height,vector<T>(sz,ti));
        build();
    }
    //[l,r)
    T prod(int l,int r){
        r--;
        if(l==r)return v[l];
        int k=height-msb(l^r)-1;
        return f(data[k][l],data[k][r]);
    }
};
template<class T,class F>
DisjointSparseTable<T,F> get_DST(vector<T> v,F f,T ti){
    return DisjointSparseTable<T,F>(v,f,ti);
}
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=300;
    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_DST(ett,[](pii a,pii b){return min(a,b);},{-INFI,-INFI});
    auto lca=[&](int u,int v){
        return st.prod(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)];
    };
    /*
    rep(i,0,n){
        cout<<in[i]<<' ';
    }
    cout<<endl;*/
    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.resize(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<<u<<' '<<k<<' '<<dist(u,k)<<endl;
                    }
                }
                //cout<<endl;
                cout<<ans<<endl;
            }
        }
    }
    return 0;
}
/*

*/
0