kmjp's blog

競技プログラミング参加記です

Codeforces #969 : Div1 B. Iris and the Tree

まぁまぁ良かった回。
https://codeforces.com/contest/2006/problem/B

問題

根付き木が与えられる。
また、この木はDFS訪問順に番号が振られている。

各辺eには、非負整数値コストT[e]があり、その和はWだとする。

以下のクエリが行われるので、そのつど、点i-(i+1)間のパスのコストを最大値の総和を求めよ。
各パスのコストを求めるとき、未定の辺のコストは個別に最適に割り振ってよい。

  • コストが未知の1つの辺を1つ確定させる。

解法

各辺は全パスにおいていずれも2回だけカウントされる。
逆に1つ辺のコストが確定すると、それにより影響を受けるパスは高々2個である。

まず、各辺のコストが定まったときに影響を受ける2つのパスを明らかにしよう。
また、各パスの最大値を求めるとき、未確定の辺が1個でもあれば、未割当のコストをそこに全振りしてよい。

割り当て済みのコストをF、未確定の辺が1個でもあるパスをn個とすると、解はF+(W-F)*n。
辺の内容を確定させながら、Fとnの更新差分を求めて行こう。

int T;
int N;
ll W;
int P[202020],D[202020];
vector<int> E[202020];
ll V[202020];
int NE[202020];
vector<int> ev[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>W;
		FOR(i,N) {
			E[i].clear();
			ev[i].clear();
			V[i]--;
			NE[i]=0;
		}
		for(i=1;i<N;i++) {
			cin>>P[i];
			P[i]--;
			D[i]=D[P[i]]+1;
			E[P[i]].push_back(i);
		}
		FOR(i,N) {
			x=i;
			y=(x+1)%N;
			while(D[x]>D[y]) {
				ev[x].push_back(i);
				x=P[x];
				NE[i]++;
			}
			while(D[x]<D[y]) {
				ev[y].push_back(i);
				y=P[y];
				NE[i]++;
			}
			while(x!=y) {
				ev[y].push_back(i);
				y=P[y];
				ev[x].push_back(i);
				x=P[x];
				NE[i]+=2;
			}
		}
		
		ll unfix=W*N;
		ll fix=0;
		int num=N;
		FOR(i,N-1) {
			ll X,Y;
			cin>>X>>Y;
			X--;
			FORR(v,ev[X]) {
				fix+=Y;
				NE[v]--;
				if(NE[v]==0) num--;
			}
			W-=Y;
			ll sum=fix+W*num;
			cout<<sum<<" ";
		}
		cout<<endl;
	}
}

まとめ

Bにしてはちょっと面倒だと思ったら、やっぱり1250ptだったか。