CF 701 E - Connecting Universities
問題
問題概要
頂点数の木があり、頂点にはからの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、個の頂点番号が指定される。それらをとする。これら個の頂点から、個のペアを作る。そのペアの木における距離の総和を最大化するようにペアを作った時、その総和の値を求めよ。
アイデア
頂点を根として考える。すると、DFSによって次の値を各頂点に対して求めることが出来る:
- : 頂点iを根とした部分木以下にある指定されている頂点の個数(自分も含む)
最適なペアを取ることの出来る状況を考えてみる。
そこで、頂点とその親の間にある辺を考えてみると、その辺は個のペアのパス上にあることになると言える。これはなぜかというと、まず、これ以上のペアのパス上になることは、この辺を挟んだ位置にあるそれぞれの頂点の個数を考えてみると、物理的に有り得ない。逆にこれ未満である状況を考えると、を根とする部分木の中にある頂点同士とがペアになっており、その部分木には含まれない頂点同士とがペアになっているということになる。そして、木の性質上、このペアをと、とに変えることでからへのパス上の辺とからへのパス上の辺を全てカバーでき、かつパスを長くすることが出来る組み合わせなのでこのような組み合わせは最適ではないことが分かり、上記のことは正しいということが分かった。
ということで、結論はということになる。
そのようなマッチングを求めることもそんなに改変しなくてもできるよって書いてあるけど、パッとは思いつけない…
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second const int V=200000; vector<int> G[V]; int n,k; int u[V]={}; int s[V]; int dfs(int now, int p) { if(s[now]>=0) return s[now]; int ret=u[now]; rep(i,G[now].size()) { int nx=G[now][i]; if(nx == p) continue; ret += dfs(nx,now); } return s[now]=ret; } int main() { scanf(" %d %d", &n, &k); rep(i,2*k) { int a; scanf(" %d", &a); --a; u[a]=1; } rep(i,n-1) { int x,y; scanf(" %d %d", &x, &y); --x; --y; G[x].pb(y); G[y].pb(x); } memset(s,-1,sizeof(s)); dfs(0,0); ll ans=0; rep(i,n) ans += min(s[i],2*k-s[i]); cout << ans << endl; return 0; }