結果

問題 No.3442 Good Vertex Connectivity
コンテスト
ユーザー kotatsugame
提出日時 2026-02-06 21:50:04
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,278 ms / 3,000 ms
コード長 3,582 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,569 ms
コンパイル使用メモリ 114,444 KB
実行使用メモリ 56,992 KB
最終ジャッジ日時 2026-02-06 21:51:07
合計ジャッジ時間 54,940 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<set>
#include<cassert>
#include<atcoder/fenwicktree>
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];
	}
};
int N;
vector<int>G[2<<17];
vector<int>V;
int L[2<<17],R[2<<17];
void dfs(int u,int p)
{
	L[u]=V.size();
	V.push_back(u);
	for(int v:G[u])if(v!=p)dfs(v,u);
	R[u]=V.size();
}
bool C[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	LCA lca(N);
	for(int i=1;i<N;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		lca.add_edge(a,b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	lca.build(0);
	dfs(0,-1);
	set<int>S;
	for(int i=0;i<N;i++)
	{
		int c;cin>>c;
		C[i]=c==1;
		if(C[i])S.insert(L[i]);
	}
	atcoder::fenwick_tree<long>BIT(N);
	for(auto it=S.begin();it!=S.end()&&next(it)!=S.end();it++)
	{
		int u=*it;
		int v=*next(it);
		BIT.add(u,lca.dist(V[u],V[v]));
	}
	int Q;cin>>Q;
	for(;Q--;)
	{
		int op;cin>>op;
		if(op==1)
		{
			int u;cin>>u;u--;
			if(!C[u])
			{
				auto it=S.lower_bound(L[u]);
				int l=-1,r=-1;
				if(it!=S.end())r=*it;
				if(it!=S.begin())l=*prev(it);
				if(l!=-1&&r!=-1)BIT.add(l,-lca.dist(V[l],V[r]));
				if(l!=-1)BIT.add(l,lca.dist(V[l],u));
				if(r!=-1)BIT.add(L[u],lca.dist(u,V[r]));
				S.insert(L[u]);
				C[u]=true;
			}
			else
			{
				auto it=S.find(L[u]);
				assert(it!=S.end());
				int l=-1,r=-1;
				it=S.erase(it);
				if(it!=S.end())r=*it;
				if(it!=S.begin())l=*prev(it);
				if(l!=-1)BIT.add(l,-lca.dist(V[l],u));
				if(r!=-1)BIT.add(L[u],-lca.dist(u,V[r]));
				if(l!=-1&&r!=-1)BIT.add(l,lca.dist(V[l],V[r]));
				C[u]=false;
			}
		}
		else
		{
			int x,y;cin>>x>>y;x--,y--;
			vector<pair<int,int> >E;
			if(x==y)E.push_back(make_pair(0,N));
			else if(lca.lca(x,y)==y)
			{
				int u=x;
				int d=lca.depth[x]-lca.depth[y]-1;
				assert(d>=0);
				for(int k=0;k<lca.parent.size();k++)if(d>>k&1)u=lca.parent[k][u];
				E.push_back(make_pair(0,L[u]));
				E.push_back(make_pair(R[u],N));
			}
			else E.push_back(make_pair(L[y],R[y]));
			long ans=0;
			vector<pair<int,int> >A;
			//cout<<"S =";
			//for(int u:S)cout<<" "<<V[u]+1;cout<<"\n";
			for(int i=0;i<E.size();i++)
			{
				auto it=S.lower_bound(E[i].first);
				if(it==S.end()||*it>=E[i].second)continue;
				auto jt=S.lower_bound(E[i].second);
				assert(jt!=S.begin());
				jt--;
				ans+=BIT.sum(*it,*jt);
				//cout<<"["<<*it<<", "<<*jt<<")"<<"\n";
				A.push_back(make_pair(V[*it],V[*jt]));
				//cout<<"("<<A.back().first+1<<", "<<A.back().second+1<<")\n";
			}
			for(int i=0;i<A.size();i++)
			{
				ans+=lca.dist(A[i].second,A[(i+1)%A.size()].first);
			}
			if(ans==0&&A.empty())cout<<"0\n";
			else cout<<ans/2+1<<"\n";
		}
	}
}
0