M-SOLUTIONS プロコンオープン : D - Maximum Sum of Minimum

まぁこれはあまり迷わないかな…。
https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d

問題

木を成す無向グラフが与えられる。
頂点数と同要素数の整数列Cが与えられる。
Cの値を1つずつ任意の頂点に割り当てたとする。

辺のスコアを、両端の頂点に割り当てた値の小さい方とする。
総スコアが最大となる割り当て方を構築せよ。

解法

次数の多い点に小さい値を割り当てると、多くの辺のスコアが小さくなって損をする。
よって逆に未確定の頂点・辺のうち、次数1の点から値を割り当てていけばよい。

int N;
set<int> S[101010];
int T[101010];
vector<int> C;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		S[x-1].insert(y-1);
		S[y-1].insert(x-1);
	}
	FOR(i,N) {
		cin>>x;
		C.push_back(x);
	}
	sort(ALL(C));
	set<pair<int,int>> cand;
	FOR(i,N) cand.insert({(int)S[i].size(),i});
	ll ret=0;
	FORR(c,C) {
		x=cand.begin()->second;
		cand.erase(cand.begin());
		T[x]=c;
		ret+=1LL*c*S[x].size();
		FORR(s,S[x]) {
			cand.erase({(int)S[s].size(),s});
			S[s].erase(x);
			cand.insert({(int)S[s].size(),s});
		}
	}
	
	cout<<ret<<endl;
	FOR(i,N) cout<<T[i]<<" ";
	cout<<endl;
	
	
}

まとめ

企業コンのDとしては簡単な気がする。