#301838 (C++17) No.772 Dynamic Distance Sum

提出ソース

結果

問題	No.772 Dynamic Distance Sum
ユーザー	maroon_kuri
提出日時	2018-12-05 23:25:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	19,384 bytes
コンパイル時間	4,406 ms
コンパイル使用メモリ	238,360 KB
実行使用メモリ	40,552 KB
最終ジャッジ日時	2024-09-25 08:13:21
合計ジャッジ時間	28,036 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	2 ms 6,940 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In static member function 'static bool Info::Select(ll, ll, Info, ll, ll, Info, ClusterType)':
main.cpp:892:9: warning: control reaches end of non-void function [-Wreturn-type]
  892 |         }
      |         ^

ソースコード

raw source code

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

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

enum ClusterType{
	NONE,
	BASE,
	RAKE,
	COMPRESS,
	HARDRAKE,
	SELECTRAKE
};
template<class Info>
struct TopTree{
	struct Cluster{
		TopTree* belongingTree;
		ClusterType type;
		Cluster *l,*r,*m,*p;
		Info info,tmpInfo;
		int a,b;
		Cluster(TopTree* tree):info(-1,-1),tmpInfo(-1,-1){
			belongingTree=tree;
			Clear();
		}
		void Clear(){
			type=NONE;
			l=nullptr;
			r=nullptr;
			m=nullptr;
			p=nullptr;
			info=Info(-1,-1);
			tmpInfo=Info(-1,-1);
			a=-1;
			b=-1;
		}
		void UpdateHandles(){
			if(type==BASE){
				belongingTree->handles[a]=this;
				belongingTree->handles[b]=this;
			}else if(type==COMPRESS){
				belongingTree->handles[l->a]=this;
				belongingTree->handles[l->b]=this;
				belongingTree->handles[r->a]=this;
				belongingTree->handles[r->b]=this;
			}
		}
		void Update(){
			if(type==COMPRESS){
				if(m){
					tmpInfo=Info(l->a,l->b);
					tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
				}
				a=l->a;
				b=r->b;
				UpdateHandles();
				info=Info(a,b);
				info.Join(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
			}else if(type==RAKE){
				a=r->a;
				b=r->b;
				info=Info(a,b);
				info.Join(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
			}else if(type==HARDRAKE){
				int la=l->a,lb=l->b;
				int ra=r->a,rb=r->b;
				if(la==ra||la==rb)swap(la,lb);
				if(lb==ra)swap(ra,rb);
				a=ra;
				b=rb;
				info=Info(a,b);
				info.Join(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
			}
		}
		void Reverse(){
			swap(a,b);
		}
		void Normalize(){
			if(type==BASE){
			}else{
				if(type==COMPRESS){
					bool updMid=false;
					if(r->a==a||r->b==a){
						swap(l,r);
						updMid=true;
					}
					if(l->a!=a)l->Reverse();
					if(r->b!=b)r->Reverse();
					if(m&&updMid){
						tmpInfo=Info(l->a,l->b);
						tmpInfo.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
					}
					info.Split(a,b,l->a,l->b,m?tmpInfo:l->info,r->a,r->b,r->info,COMPRESS);
					if(m)tmpInfo.Split(l->a,l->b,m->a,m->b,m->info,l->a,l->b,l->info,RAKE);
				}else if(type==RAKE){
					info.Split(a,b,l->a,l->b,l->info,r->a,r->b,r->info,RAKE);
				}else if(type==HARDRAKE){
					int la=l->a,lb=l->b;
					int ra=r->a,rb=r->b;
					if(la==ra||la==rb)swap(la,lb);
					if(lb==ra)swap(ra,rb);
					info.Split(a,b,la,lb,l->info,ra,rb,r->info,RAKE);
				}
			}
		}
		Cluster* Select(int&xa,int&xb,Info&x,int&ya,int&yb,Info&y){
			Normalize();
			if(type==BASE){
				return this;
			}else{
				if(type==COMPRESS){
					Info lTmp(l->b,l->a),rTmp(r->a,r->b);
					if(xa==xb)lTmp=l->info;
					else lTmp.Join(l->b,l->a,xa,xb,x,l->b,l->a,l->info,SELECTRAKE);
					if(ya==yb)rTmp=r->info;
					else rTmp.Join(r->a,r->b,yb,ya,y,r->a,r->b,r->info,SELECTRAKE);
					if(m){
						Info mTmp(l->a,l->b);
						mTmp.Join(l->a,l->b,m->a,m->b,m->info,l->a,l->b,lTmp,RAKE);
						bool s=Info::Select(l->a,l->b,mTmp,r->a,r->b,rTmp,COMPRESS);
						if(s){
							xa=l->a,xb=l->b,x=mTmp;
							return r;
						}else{
							mTmp=Info(m->a,m->b);
							mTmp.Join(m->a,m->b,r->b,r->a,rTmp,m->a,m->b,m->info,RAKE);
							s=Info::Select(m->a,m->b,mTmp,l->a,l->b,lTmp,RAKE);
							if(s){
								ya=m->b,yb=m->a,y=mTmp;
								return l;
							}else{
								Info lrTmp(r->b,r->a);
								lrTmp.Join(r->b,r->a,l->a,l->b,lTmp,r->b,r->a,rTmp,RAKE);
								xa=m->a,xb=m->a,x=Info(-1,-1),ya=r->a,yb=r->b,y=lrTmp;
								return m;
							}
						}
					}else{
						bool s=Info::Select(l->a,l->b,lTmp,r->a,r->b,rTmp,COMPRESS);
						if(s){
							xa=l->a,xb=l->b,x=lTmp;
							return r;
						}
						else{
							ya=r->a,yb=r->b,y=rTmp;
							return l;
						}
					}
				}else if(type==RAKE){
					Info w(l->a,l->b);
					if(ya==yb)w=l->info;
					else w.Join(l->a,l->b,yb,ya,y,l->a,l->b,l->info,SELECTRAKE);
					bool s=Info::Select(l->a,l->b,w,r->a,r->b,r->info,RAKE);
					if(s){
						xa=r->a,xb=r->a,x=Info(-1,-1),ya=l->b,yb=l->a,y=w;
						return r;
					}else{
						w=Info(r->a,r->b);
						if(ya==yb)w=r->info;
						else w.Join(r->a,r->b,yb,ya,y,r->a,r->b,r->info,RAKE);
						xa=l->a,xb=l->a,x=Info(-1,-1),ya=r->b,yb=r->a,y=w;
						return l;
					}
				}else if(type==HARDRAKE){
					int la=l->a,lb=l->b;
					int ra=r->a,rb=r->b;
					if(la==ra||la==rb)swap(la,lb);
					if(lb==ra)swap(ra,rb);
					Info lTmp(la,lb),rTmp(ra,rb);
					if(ya==yb)lTmp=l->info;
					else lTmp.Join(la,lb,yb,ya,y,la,lb,l->info,SELECTRAKE);
					if(xa==xb)rTmp=r->info;
					else rTmp.Join(rb,ra,xa,xb,x,rb,ra,r->info,SELECTRAKE);
					bool s=Info::Select(la,lb,lTmp,ra,rb,rTmp,RAKE);
					if(s){
						if(ra==r->a){
							ya=lb,yb=la,y=lTmp;
							return r;
						}else{
							ya=xb,yb=xa,y=x;
							xa=la,xb=lb,x=lTmp;
							return r;
						}
					}else{
						lTmp=Info(ra,rb);
						if(ya==yb)lTmp=rTmp;
						else lTmp.Join(ra,rb,yb,ya,y,ra,rb,rTmp,RAKE);
						if(la==l->a){
							xa=la,xb=la,x=Info(-1,-1),ya=rb,yb=ra,y=lTmp;
							return l;
						}else{
							xa=ra,xb=rb,x=lTmp,ya=la,yb=la,y=Info(-1,-1);
							return l;
						}
					}
				}
			}
			assert(false);
		}
		int Pos(){
			Cluster *x=p;
			if(!x)return 0;
			else if(x->l==this)return -1;
			else if(x->r==this)return 1;
			else if(x->m==this)return -2;
			assert(false);
		}
		bool LinkedToParent(){
			return p&&(p->type!=type||p->m==this);
		}
		void Rotate(){
			Cluster *q=p,*c;
			if(Pos()==1){
				c=l;
				l=q;
				q->r=c; 
			}else{
				c=r;
				r=q;
				q->l=c;
			}
			if(c){
				if(c->p)c->p=q;
			}
			int w=p->Pos();
			p=p->p;
			q->p=this;
			Cluster *x=p;
			if(x){
				if(w==1)x->r=this;
				else if(w==-1)x->l=this;
				else if(w==-2)x->m=this;
			}
			q->Update();
		}
		void Splay(Cluster* guard){
			while(p&&p!=guard&&!LinkedToParent()){
				Cluster *q=p->p;
				if(q&&q!=guard&&!p->LinkedToParent()){
					if(Pos()==p->Pos()){
						p->Rotate();
					}else{
						Rotate();
					}
					Rotate();
				}else{
					Rotate();
				}
			}
			Update();
		}
		void Destroy(){
			info.Destroy(a,b);
		}
	};
	vector<Cluster*> handles;
	vector<Cluster> clusterBuf;
	vi ptrBuf;
	vi deg;
	vector<Cluster*> hardRakeClusters,needUpdateClusters;
	Cluster* selectRoot;
	TopTree(){}
	TopTree(int n){
		Init(n);
	}
	int vertNum,edgeNum;
	void Init(int n){
		int s=n*2+10;
		clusterBuf=vector<Cluster>(s,Cluster(this));
		REP(i,s)ptrBuf.PB(i);
		deg=vi(n,0);
		handles=vector<Cluster*>(n,nullptr);
		vertNum=n;
		edgeNum=0;
		selectRoot=nullptr;
	}
	Cluster* GetNew(){
		Cluster *res=clusterBuf.data()+ptrBuf.back();
		ptrBuf.pop_back();
		res->Clear();
		return res;
	}
	void Recycle(Cluster* ptr){
		ptrBuf.PB(ptr-clusterBuf.data());
	}
	void ClearHardRakeClusters(){
		while(!hardRakeClusters.empty()){
			Cluster* x=hardRakeClusters.back();
			hardRakeClusters.pop_back();
			x->Normalize();
			Recycle(x);
		}
		while(!needUpdateClusters.empty()){
			Cluster* x=needUpdateClusters.back();
			needUpdateClusters.pop_back();
			x->Update();
		}
	}
	void Rectify(Cluster* x,Cluster* guard){
		Cluster* p=x->p;
		if(p!=nullptr){
			Rectify(p,guard);
			if(p==guard&&p->r==x){
				p->Reverse();
				p->Normalize();
			}
		}
		x->Normalize();
	}
	Cluster* CreateCompressCluster(Cluster*l,Cluster*r,Cluster*m){
		auto p=GetNew();
		p->type=COMPRESS;
		p->l=l;
		l->p=p;
		p->r=r;
		r->p=p;
		p->m=m;
		if(m){
			m->p=p;
		}
		p->Update();
		return p;
	}
	Cluster* CreateRakeCluster(Cluster*l,Cluster*r){
		if(!l)return r;
		if(!r)return l;
		auto p=GetNew();
		p->type=RAKE;
		p->l=l;
		l->p=p;
		p->r=r;
		r->p=p;
		p->Update();
		return p;
	}
	Cluster* CreateHardRakeCluster(Cluster*l,Cluster*r){
		if(!l)return r;
		auto p=GetNew();
		hardRakeClusters.PB(p);
		p->type=HARDRAKE;
		p->l=l;
		p->r=r;
		p->Update();
		return p;
	}
	void SoftExpose(int v,Cluster* guard){
		if(handles[v]==guard)return;
		Rectify(handles[v],guard);
		Cluster *x=handles[v],*tmp=x;
		if(x->type==COMPRESS)x->Splay(guard);
		while(x->LinkedToParent()){
			Cluster* p=x->p;
			if(p->type==RAKE){
				p->Splay(nullptr);
				if(x->p!=p)
					x->p->Splay(p);
				x=p;
			}
			x=x->p;
			x->Splay(guard);
		}
		x=tmp;
		while(x->LinkedToParent()){
			Cluster* m=nullptr;
			Cluster* y=x->p;
			if(y->type==RAKE){
				Cluster*p=x->p;
				if(x->Pos()<0){
					m=p->r;
				}else{
					m=p->l;
				}
				y=p->p;
				if(y->type==RAKE){
					Cluster*q=p->p;
					if(p->Pos()<0){
						m=CreateRakeCluster(m,q->r);
					}else{
						m=CreateRakeCluster(m,q->l);
					}
					y=q->p;
					Recycle(q);
				}
				Recycle(p);
			}
			m=CreateRakeCluster(m,y->l);
			y->l->UpdateHandles();
			y->l=x;
			x->p=y;
			y->m=m;
			m->p=y;
			y->Update();
			x=y;
		}
		if(tmp->type==BASE)tmp=tmp->p;
		if(tmp){
			tmp->Splay(guard);
		}
		if(guard)guard->Update();
	}
	bool SoftExpose(int a,int b){
		if(deg[b]==0){
			return false;
		}else if(deg[a]==0){
			SoftExpose(b,nullptr);
			if(handles[b]->a==b){
				handles[b]->Reverse();
				handles[b]->Normalize();
			}
			return false;
		}else if(deg[b]==1){
			SoftExpose(b,nullptr);
			if(handles[b]->a==b){
				handles[b]->Reverse();
				handles[b]->Normalize();
			}
			SoftExpose(a,nullptr);
			if(handles[a]==handles[b]){
				return true;
			}else{
				if(handles[a]->a==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				return false;
			}
		}else{
			SoftExpose(b,nullptr);
			SoftExpose(a,handles[b]);
			if(handles[a]==handles[b]){
				if(handles[a]->b==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				return true;
			}else if(handles[a]==handles[b]->l){
				return true;
			}else{
				if(handles[a]->a==a){
					handles[a]->Reverse();
					handles[a]->Normalize();
				}
				return false;
			}
		}
	}
	void SoftExpose(int v){
		if(deg[v]==0){
			//do nothing
		}else{
			SoftExpose(v,nullptr);
			if(handles[v]->a==v){
				handles[v]->Reverse(); 
				handles[v]->Normalize();
			}
		}
	}
	Cluster* HardExpose(int a,int b){
		if(deg[b]==1){
			return handles[a];
		}else if(deg[a]==1){
			needUpdateClusters.PB(handles[b]);
			auto x=handles[b]->l;
			x=CreateHardRakeCluster(handles[b]->m,x);
			x=CreateHardRakeCluster(handles[b]->r,x);
			return x;
		}else{
			needUpdateClusters.PB(handles[b]);
			needUpdateClusters.PB(handles[a]);
			auto x=handles[a]->r;
			x=CreateHardRakeCluster(handles[a]->l,x);
			x=CreateHardRakeCluster(handles[a]->m,x);
			x=CreateHardRakeCluster(handles[b]->m,x);
			x=CreateHardRakeCluster(handles[b]->r,x);
			return x;
		}
	}
	Cluster* HardExpose(int v){
		return HardExpose(handles[v]->a,v);
	}
	Cluster* ExposePath(int a,int b){
		assert(!selectRoot);
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		bool connected=SoftExpose(a,b);
		if(!connected)return nullptr;
		return HardExpose(a,b);
	}
	Info* Expose(int a,int b){
		//cerr<<"expose "<<a<<" "<<b<<endl;
		if(a==b)return Expose(a);
		Cluster*x=ExposePath(a,b);
		if(x)return &(x->info);
		else return nullptr;
	}
	Cluster* ExposeVertex(int v){
		assert(!selectRoot);
		ClearHardRakeClusters();
		SoftExpose(v);
		if(deg[v]==0)return nullptr;
		return HardExpose(v);
	}
	Info* Expose(int v){
		//cerr<<"expose "<<v<<endl;
		Cluster*x=ExposeVertex(v);
		if(x)return &(x->info);
		else return nullptr;
	}
	bool Connected(int a,int b){
		//cerr<<"connected "<<a<<" "<<b<<endl;
		assert(!selectRoot);
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		return SoftExpose(a,b);
	}
	template <class... Args>
	bool Link(int a,int b,Args... args){
		assert(!selectRoot);
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		//cerr<<"link "<<a<<" "<<b<<endl;
		bool connected=SoftExpose(a,b);
		if(connected)return false;
		Cluster* u=handles[a],*v=handles[b];
		Cluster* x=GetNew();
		x->type=BASE;
		x->a=a;
		x->b=b;
		x->info=Info(a,b);
		x->info.Create(a,b,args...);
		x->UpdateHandles();
		Cluster* y=nullptr;
		if(deg[a]==0){
			y=x;
		}else if(deg[a]==1){
			y=CreateCompressCluster(u,x,nullptr);
		}else{
			u->r->Reverse();
			u->r->UpdateHandles();
			y=CreateCompressCluster(u->l,x,CreateRakeCluster(u->r,u->m));
			Recycle(u);
		}
		if(deg[b]==0){
		}else if(deg[b]==1){
			v->Reverse();
			v->Normalize();
			CreateCompressCluster(y,v,nullptr);
		}else{
			v->l->UpdateHandles();
			CreateCompressCluster(y,v->r,CreateRakeCluster(v->m,v->l));
			Recycle(v);
		}
		deg[a]++;
		deg[b]++;
		edgeNum++;
		return true;
	}
	pair<Cluster*,Cluster*> SplitMiddleChild(Cluster*x){
		if(x->type!=RAKE)return MP(x,nullptr);
		while(x->type==RAKE)x=x->l;
		x->p->Splay(nullptr);
		Cluster* tmp=x->p;
		pair<Cluster*,Cluster*>  res=MP(tmp->l,tmp->r);
		Recycle(tmp);
		return res;
	}
	bool Cut(int a,int b){
		assert(!selectRoot);
		ClearHardRakeClusters();
		if(deg[a]>deg[b])swap(a,b);
		//cerr<<"cut "<<a<<" "<<b<<endl;
		bool connected=SoftExpose(a,b);
		if(!connected)return false;
		Cluster *u=handles[a],*v=handles[b];
		if(deg[b]==1){
			if(u->type!=BASE)return false;
			u->Destroy();
			Recycle(u);
			handles[a]=nullptr;
			handles[b]=nullptr;
		}else if(deg[a]==1){
			if(v->l->type!=BASE)return false;
			if(deg[b]==2){
				v->r->p=nullptr;
				v->r->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
				CreateCompressCluster(z.first,v->r,z.second);
			}
			v->l->Destroy();
			Recycle(v->l);
			Recycle(v);
			handles[a]=nullptr;
		}else{
			if(u->r->type!=BASE)return false;
			if(deg[a]==2){
				u->l->p=nullptr;
				u->l->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(u->m);
				z.first->Reverse();
				CreateCompressCluster(u->l,z.first,z.second);
			}
			if(deg[b]==2){
				v->r->p=nullptr;
				v->r->UpdateHandles();
			}else{
				pair<Cluster*,Cluster*> z=SplitMiddleChild(v->m);
				CreateCompressCluster(z.first,v->r,z.second);
			}
			u->r->Destroy();
			Recycle(u->r);
			Recycle(u);
			Recycle(v);
		}
		deg[a]--;
		deg[b]--;
		edgeNum--;
		return true;
	}
	Info* PrepareForSelect(int a,int b){
		//cerr<<"prepare "<<a<<" "<<b<<endl;
		if(a==b)return PrepareForSelect(a);
		selectRoot=ExposePath(a,b);
		if(selectRoot==nullptr)return nullptr;
		return &(selectRoot->info);
	}
	Info* PrepareForSelect(int v){
		//cerr<<"prepare "<<v<<endl;
		selectRoot=ExposeVertex(v);
		if(selectRoot==nullptr)return nullptr;
		return &(selectRoot->info);
	}
	Info* Select(){
		assert(selectRoot);
		assert(!selectRoot->p);
		Cluster* cur=selectRoot;
		int xa=cur->a,xb=xa,ya=cur->b,yb=ya;
		Info x(-1,-1),y(-1,-1);
		while(1){
			Cluster*nx=cur->Select(xa,xb,x,ya,yb,y);
			if(nx==cur)break;
			cur=nx;
		}
		selectRoot=nullptr;
		return Expose(cur->a,cur->b);
	}
	int NumofVertices(){
		return vertNum;
	}
	int NumofEdges(){
		return edgeNum;
	}
};

struct InfoBase{
	private:
	int vert[2];
	void SetVertex(int a,int b){
		vert[0]=a;
		vert[1]=b;
	}
	public:
	InfoBase(int a,int b){
		SetVertex(a,b);
	}
	inline int idx(int v){
		if(vert[0]==v)return 0;
		if(vert[1]==v)return 1;
		assert(false);
	}
	inline int another(int v){
		if(vert[0]==v)return vert[1];
		if(vert[1]==v)return vert[0];
		assert(false);
	}
	inline int v0(){
		return vert[0];
	}
	inline int v1(){
		return vert[1];
	}
};

const int Nmax=100010;
int x[Nmax];

struct Info:InfoBase{
	Info(int a,int b):InfoBase(a,b){}
	int s,p,_ds[2];
	int&ds(int v){
		return _ds[idx(v)];
	}
	int GetAns(){
		return min(_ds[0]+x[v1()]*p,_ds[1]+x[v0()]*p);
	}
	int GetMarked(){
		return x[v0()]+x[v1()]+s;
	}
	void Join(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
		//(another(a)==b);
		//(another(b)==a);
		if(type==RAKE){
			//(a==ra);
			//(b==rb);
			//(lb==rb);
			s=l.s+r.s+x[la];
			p=r.p;
			ds(a)=r.ds(a)+l.ds(b)+r.p*l.s+x[la]*(r.p+l.p);
			ds(b)=r.ds(b)+l.ds(b)+x[la]*l.p;
		}else if(type==SELECTRAKE){
			//(a==ra);
			//(b==rb);
			//(lb==rb);
			s=l.s+r.s+x[la];
			p=r.p;
			ds(a)=r.ds(a)+l.ds(b)+r.p*l.s+x[la]*(r.p+l.p);
			ds(b)=r.ds(b)+l.ds(b)+x[la]*l.p;
		}else if(type==COMPRESS){
			//(a==la);
			//(lb==ra);
			//(rb==b);
			s=l.s+r.s+x[lb];
			p=l.p+r.p;
			ds(a)=l.ds(a)+r.ds(ra)+l.p*r.s+x[lb]*l.p;
			ds(b)=l.ds(lb)+r.ds(b)+r.p*l.s+x[lb]*r.p;
		}
	}
	void Create(int a,int b,int c){
		//(another(a)==b);
		//(another(b)==a);
		s=0;
		p=c;
		ds(a)=ds(b)=0;
	}
	void Split(int a,int b,int la,int lb,Info&l,int ra,int rb,Info&r,ClusterType type){
		//(another(a)==b);
		//(another(b)==a);
		if(type==RAKE){
			//(a==ra);
			//(b==rb);
			//(lb==rb);
		}else if(type==COMPRESS){
			//(a==la);
			//(lb==ra);
			//(rb==b);
		}
	}
	void Destroy(int a,int b){
		//(another(a)==b);
		//(another(b)==a);
	}
	//条件を満たすものが一つでもrに含まれていればtrueを返す
	static bool Select(int la,int lb,Info l,int ra,int rb,Info r,ClusterType type){
		if(type==RAKE){
			//(lb==rb);
			return l.GetMarked()<=r.GetMarked();
		}else if(type==COMPRESS){
			//(lb==ra);
			return l.GetMarked()<=r.GetMarked();
		}
	}
};

signed main(){
	int n=read();
	REP(i,n)
		x[i]=1;
	TopTree<Info> tree(n);
	int q=read();
	REP(_,q){
		int t=read();
		if(t==1){
			int a=read()-1,b=read()-1,c=read();
			tree.Link(a,b,c);
		}else if(t==2){
			int a=read()-1,b=read()-1;
			tree.Cut(a,b);
		}else if(t==3){
			int a=read()-1;
			auto info=tree.PrepareForSelect(a);
			x[a]^=1;
			if(info==nullptr){
				print(0);
			}else{
				info=tree.Select();
				print(info->GetAns());
			}
		}else{
			assert(false);
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード