Codeforces #864 : Div2 F. Li Hua and Path

特にコメントもないな。
https://codeforces.com/contest/1797/problem/F

問題

N頂点の木を成す無向グラフが与えられる。
頂点対(u,v)がcuteであるとは、u-vのパスのうち、uのラベルが最小値、vのラベルが最大値であるものをいう。

ここでM個のクエリが与えられる。
j番目のクエリでは、(N+j)番の頂点が追加され、既存の点との間に辺が張られる。
その都度、cuteな頂点対の総数を答えよ。

解法

元の木について2つの変形を考える。
max-RTは、ラベルの小さい順に、「自身の連結成分に隣接する点のうち最小のラベルのもの」に辺を張ったものである。
min-RTは、大小逆に同じ作業を行ったもの。

前者でvがuの祖先であり、後者でuがvの祖先であるものの組み合わせが解となる。
頂点を増やしながら、これらの増分を数え上げて行こう。

int N,M;
vector<int> E[404040],RE[404040];
vector<int> maE[404040],miE[404040];
int maP[404040],miP[404040],T[404040];
int maD[404040],miD[404040];
int L[404040],R[404040];
int id;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<404040> uf;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

ll ret;
int num;
void dfs1(int cur) {
	L[cur]=id++;
	if(cur!=N-1) maD[cur]=maD[maP[cur]]+1;
	else maD[cur]=1;
	ret+=maD[cur]-1;
	FORR(e,maE[cur]) dfs1(e);
	R[cur]=id;
}
void dfs2(int cur) {
	if(cur!=0) miD[cur]=miD[miP[cur]]+1;
	else miD[cur]=1;
	ret+=miD[cur]-1;
	ret-=2*(bt(R[cur]-1)-bt(L[cur]-1));
	bt.add(L[cur],1);
	FORR(e,miE[cur]) dfs2(e);
	bt.add(L[cur],-1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		E[x].push_back(y);
		RE[y].push_back(x);
	}
	FOR(i,N) {
		T[i]=i;
		FORR(e,RE[i]) {
			e=uf[e];
			uf(e,i);
			maP[T[e]]=i;
			maE[i].push_back(T[e]);
			T[e]=i;
		}
	}
	uf.reinit();
	for(i=N-1;i>=0;i--) {
		T[i]=i;
		FORR(e,E[i]) {
			e=uf[e];
			uf(e,i);
			miP[T[e]]=i;
			miE[i].push_back(T[e]);
			T[e]=i;
		}
	}
	dfs1(N-1);
	dfs2(0);
	
	cout<<ret<<endl;
	cin>>M;
	while(M--) {
		cin>>x;
		x--;
		miD[N]=miD[x]+1;
		ret+=(N+1)-miD[N];
		N++;
		cout<<ret<<endl;
	}
	
	
}

まとめ

割と実装がしんどいかも。