Codeforces #813 : Div2 F. Triameter

自分では思いつかなそうな問題設定だな。
https://codeforces.com/contest/1712/problem/F

問題

根付き木が与えられる。
各辺の重みのは1であるとする。

以下のクエリに答えよ。

• 正整数Xが与えられるので、元の木で葉となる頂点対の間に、重さXの辺を追加する。このグラフの直径を求めよ。

解法

クエリ毎に独立に解いていこう。

元のグラフの各頂点vに対し、f(v)を最寄の葉までの距離とすると、このグラフにおける2点u,v間の距離d'(u,v)は、元のグラフの距離d(u,v)を用いて
d'(u,v) = min(F(u)+F(v)+X, d(u,v))
と置ける。

マージテクの要領で以下を保持しながら、上記値を計算していけばよい。
val(v,i) := vのsubtree中の頂点uのうち、f(u)=iとなるuの深さの最大値

int N;
int P[1010101],D[1010101];
vector<int> E[1010101];
int F[1010101];
int T,X;
int ret;
vector<int> val[2020202];

void dfs(int cur,int pre) {
	val[cur].clear();
	if(cur!=pre) D[cur]=D[pre]+1;
	int i,j;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(val[e].size()>val[cur].size()) swap(val[cur],val[e]);
		
		FOR(i,val[e].size()) {
			while(1) {
				int j=max(0,ret-i-X);
				if(j>=val[cur].size()) break;
				if(val[e][i]+val[cur][j]-2*D[cur]<ret) break;
				ret++;
			}
		}
		FOR(i,val[e].size()) val[cur][i]=max(val[cur][i],val[e][i]);
	}
	while(1) {
		int j=max(0,ret-F[cur]-X);
		if(j>=val[cur].size()) break;
		if(D[cur]+val[cur][j]-2*D[cur]<ret) break;
		ret++;
	}
	if(F[cur]>=val[cur].size()) val[cur].push_back(D[cur]);
	else val[cur][F[cur]]=max(val[cur][F[cur]],D[cur]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		E[x-1].push_back(i+1);
		E[i+1].push_back(x-1);
	}
	queue<int> Q;
	FOR(i,N) {
		if(E[i].size()==1) Q.push(i);
		else F[i]=1<<30;
	}
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		FORR(e,E[cur]) if(F[e]==1<<30) {
			F[e]=F[cur]+1;
			Q.push(e);
		}
	}
	int root;
	FOR(i,N) if(E[i].size()>=2) root=i;
	
	cin>>T;
	while(T--) {
		cin>>X;
		ret=0;
		dfs(root,root);
		cout<<ret-1<<" ";
	}
	cout<<endl;
}

まとめ

時間を掛ければ解答にたどり着くかもしれないけど、実装も含めちょっとしんどいな。