kmjp's blog

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

Codeforces Global Round 19 : F. Towers

これも本番どうにか解いてるな。
https://codeforces.com/contest/1637/problem/F

問題

N頂点の木を成すグラフが与えられる。
各点vには高さH[v]が設定されている。

各点vに非負整数E[v]を割り当てたい。
その際、各点xに対し、パス上にxを含む端点(u,v)のうち、min(E[u],E[v])≧H[x]となるようにしたい。
Eの総和の最小値を求めよ。

解法

根以外の頂点vのSubTreeに対し、その中のEの総和と最大値を取るようにしよう。
vの配下にH[v]以上のものがない場合、SubTree以下で最大のE(u)に対しH[v]-E(u)だけ加算して、SubTree内にH[v]以上の点が少なくとも1個できるようにする。

根頂点rについては、同様にH[r]以上の点が2個以上できるようにすればよい。

int N;
ll H[202020];
vector<int> E[202020];

pair<ll,ll> dfs(int cur,int pre) {
	
	ll sum=0;
	if(cur!=pre) {
		ll ma=0;
		
		FORR(e,E[cur]) if(e!=pre) {
			auto p=dfs(e,cur);
			sum+=p.first;
			ma=max(ma,p.second);
		}
		
		if(H[cur]>ma) {
			sum+=H[cur]-ma;
			ma=H[cur];
		}
		return {sum,ma};
	}
	else {
		vector<ll> C={0,0};
		FORR(e,E[cur]) if(e!=pre) {
			auto p=dfs(e,cur);
			sum+=p.first;
			C.push_back(p.second);
		}
		sort(ALL(C));
		reverse(ALL(C));
		sum+=H[cur]-C[0];
		sum+=H[cur]-C[1];
		return {sum,H[cur]};
		
		
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ma=0;
	j=0;
	FOR(i,N) {
		cin>>H[i];
		ma=max(ma,H[i]);
		if(H[i]==ma) j=i;
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	auto p=dfs(j,j);
	cout<<p.first<<endl;
	
}

まとめ

まぁ割とシンプルな問題。