結果

問題 No.3189 Semifinal Stage
ユーザー kotatsugame
提出日時 2025-06-20 22:18:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,329 ms / 4,000 ms
コード長 2,183 bytes
コンパイル時間 1,092 ms
コンパイル使用メモリ 87,088 KB
実行使用メモリ 26,484 KB
最終ジャッジ日時 2025-08-06 18:14:09
合計ジャッジ時間 55,772 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#include<cassert>
using namespace std;
#include<vector>
struct LCA{
	int N;
	vector<vector<int> >G,parent;
	vector<int>depth;
	LCA(int N_=0):N(N_),G(N_),depth(N_)
	{
		int lg=0;
		while((1<<lg)+1<N_)lg++;
		parent.assign(lg+1,vector<int>(N_));
	}
	void add_edge(int u,int v)
	{
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void dfs(int u,int p,int d)
	{
		depth[u]=d;
		parent[0][u]=p;
		for(int v:G[u])if(v!=p)dfs(v,u,d+1);
	}
	void build(int root=0)
	{
		dfs(root,-1,0);
		for(int k=1;k<parent.size();k++)
		{
			for(int i=0;i<N;i++)
			{
				if(parent[k-1][i]==-1)parent[k][i]=-1;
				else parent[k][i]=parent[k-1][parent[k-1][i]];
			}
		}
	}
	int lca(int u,int v)
	{
		if(depth[u]>depth[v])swap(u,v);
		for(int k=0;k<parent.size();k++)if(depth[v]-depth[u]>>k&1)v=parent[k][v];
		if(u==v)return u;
		for(int k=parent.size();k--;)if(parent[k][u]!=parent[k][v])
		{
			u=parent[k][u];
			v=parent[k][v];
		}
		return parent[0][u];
	}
	int dist(int u,int v)
	{
		int w=lca(u,v);
		return depth[u]+depth[v]-2*depth[w];
	}
};
vector<int>Q;
int N;
vector<int>G[1<<17];
vector<int>V;
bool B[1<<17];
int dist[1<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	LCA lca(N);
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
		lca.add_edge(u,v);
	}
	lca.build(0);
	{
		int Qc;cin>>Qc;
		V.resize(Qc);
		for(int i=0;i<Qc;i++)
		{
			int o,v;cin>>o>>v;v--;
			if(o==1)V[i]=v;
			else V[i]=~v;
		}
	}
	const int W=400;
	for(int l=0;l<V.size();l+=W)
	{
		int r=min(l+W,(int)V.size());
		for(int i=0;i<N;i++)dist[i]=B[i]?0:1e9;
		set<int>S;
		for(int q=l;q<r;q++)if(V[q]>=0&&dist[V[q]]==0)dist[V[q]]=1e9,S.insert(V[q]);
		Q.clear();
		for(int i=0;i<N;i++)if(dist[i]==0)Q.push_back(i);
		for(int i=0;i<Q.size();i++)
		{
			int u=Q[i];
			for(int v:G[u])if(dist[v]>dist[u]+1)dist[v]=dist[u]+1,Q.push_back(v);
		}
		for(int q=l;q<r;q++)
		{
			if(V[q]>=0)
			{
				if(B[V[q]])B[V[q]]=false,S.erase(V[q]);
				else B[V[q]]=true,S.insert(V[q]);
			}
			else
			{
				int ans=dist[~V[q]];
				for(int u:S)ans=min(ans,lca.dist(u,~V[q]));
				cout<<ans<<"\n";
			}
		}
	}
}
0