Codeforces #958 : Div2 D. The Omnipotent Monster Killer

後半失速した回。
https://codeforces.com/contest/1988/problem/D

問題

木を成す無向グラフが与えられる。
各点には整数値が設定されている。

毎ターン、残った頂点に対しその設定の総和のダメージを食らう。
その後、任意の数の頂点を削除できるが、辺で隣接する2点は同時に消せない。
全点を削除するまでの最小総ダメージ数はいくらか。

解法

DFSで各点に対し、SubTreeの点をすべて消すまでの総ダメージについて、ダメージをSubTreeの根頂点を消すターンについて、小さい順に上位2位まで求めよう。
その親頂点の頂点を消す際、子頂点は1位か2位かどちらかのタイミングで消すことができる。

int T,N;
ll A[303030];
vector<int> E[303030];

pair<ll,int> dp1[303030];
pair<ll,int> dp2[303030];

void dfs(int cur,int pre) {
	
	map<int,ll> C;
	int i;
	for(i=1;i<=E[cur].size()+2;i++) C[i]=0;
	ll sum=0;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		sum+=dp1[e].first;
		C[dp1[e].second]+=dp2[e].first-dp1[e].first;
	}
	dp1[cur]={1LL<<60,0};
	dp2[cur]={1LL<<60,0};
	FORR2(a,b,C) {
		pair<ll,int> p={sum+b+1LL*a*A[cur],a};
		if(p<dp1[cur]) {
			dp2[cur]=dp1[cur];
			dp1[cur]=p;
		}
		else if(p<dp2[cur]) {
			dp2[cur]=p;
		}
	}
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		dfs(0,0);
		cout<<dp1[0].first<<endl;
	}
}

まとめ

これはすんなり解けて良かったね。