Codeforces #701 Div2 : E. Move and Swap

この回は普通に全完できてる。
https://codeforces.com/contest/1485/problem/E

問題

根付き木を成すグラフが与えられる。
各葉までの距離は一定である。また、各点には整数値が設定されている。

初期状態で赤と青の駒が根頂点にある。
この状態で、両駒が葉に到達するまで、以下の処理を行う。

• 赤い駒を、子頂点のいずれかに移動する。
• 青い駒を、赤い駒と同じ深さの任意の点に移動する。
• その後、両駒をswapしてもよいししなくてもよい。この時、両駒のある頂点の整数値の差の絶対値がスコアに加算される。

最適な移動順を取った場合、総スコアの最大値を求めよ。

解法

各点に赤い駒が来た場合のスコアをDPで求めて行こう。
遷移の方法は2通りあり、

• 親頂点から子頂点に赤頂点を下す。その場合、青頂点は任意の(同じ深さの)頂点を選べるので、青頂点の候補は整数値の最大値と最小値の2つ。
• 青頂点を適当に落とし、赤頂点とswapする。その場合、元の赤頂点の位置のうち、それまでの総スコアと整数値の和または差が最大のものを選ぼう。

int T;
int N;
vector<int> E[202020],C[202020];
int A[202020];

int L[202020],R[202020],D[202020],mad;
int id;
vector<int> V[202020];
ll dp[202020];

void dfs(int cur,int pre,int d) {
	D[cur]=d;
	mad=max(mad,d);
	V[d].push_back(cur);
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur,d+1);
		C[cur].push_back(e);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear(),V[i].clear(),C[i].clear(),dp[i]=-1LL<<60;
		FOR(i,N-1) {
			cin>>x;
			E[i+1].push_back(x-1);
			E[x-1].push_back(i+1);
		}
		FOR(i,N-1) cin>>A[i+1];
		
		mad=0;
		dfs(0,0,0);
		dp[0]=0;
		ll ret=-1LL<<60;
		for(int d=0;d<mad;d++) {
			//直下
			int mi=1<<30,ma=0;
			FORR(v,V[d+1]) mi=min(mi,A[v]),ma=max(ma,A[v]);
			set<ll> SP,SM;
			FORR(v,V[d]) {
				FORR(c,C[v]) {
					SP.insert(dp[v]+A[c]);
					SM.insert(-dp[v]+A[c]);
				}
			}
			FORR(v,V[d]) {
				FORR(c,C[v]) {
					dp[c]=max({dp[c],*SP.rbegin()-A[c],A[c]-*SM.begin()});
					dp[c]=max({dp[c],dp[v]+A[c]-mi,dp[v]+ma-A[c]});
					ret=max(ret,dp[c]);
				}
			}
		}
		cout<<ret<<endl;
		
		
	}
}

まとめ

丁寧にやればさほど複雑ではない問題。