Codeforces #607 Div1 C. Jeremy Bearimy

問題文が無駄にややこしい…。
https://codeforces.com/contest/1280/problem/C

問題

2N頂点からなる木を成す無向グラフが与えられる。
辺には長さが設定されている。

これらの2N頂点をN個の対に分けたとする。
同じ対に属する頂点間の最短距離の総和の最小値と最大値を求めよ。

解法

DFS順で処理していくとき、頂点vのSubTreeの頂点数をf(v)とする。

• 最小値
  • f(v)が奇数なら、vと親頂点の間に対を設置する。
• 最大値
  • vと親頂点の間の辺は、min(f(v),2N-f(v))だけ形状されるように配置できる。

int T;
int N;
vector<pair<int,int>> E[201010];
int C[202020];
ll ret[2];

int dfs(int cur,int pre) {
	C[cur]=1;
	int pd=0;
	FORR(e,E[cur]) {
		if(e.first!=pre) {
			C[cur]+=dfs(e.first,cur);
		}
		else {
			pd=e.second;
		}
	}
	
	if(C[cur]%2) ret[0]+=pd;
	ret[1]+=1LL*min(C[cur],2*N-C[cur])*pd;
	return C[cur];
}

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

まとめ

これ問題文の長さ3割ぐらいにならんかな。