問題文わかりにくすぎじゃないですかね…。
http://codeforces.com/contest/592/problem/D
問題
N頂点からなる木を成すグラフが与えられる。
各辺の長さは1である。
ここでM個の頂点が指定される。
任意の頂点から開始し、指定された頂点を最低1回ずつ通りたい。
移動距離を最小化するには、どの頂点から開始すればよいか。またその時の移動距離を求めよ。
解法
まず、指定された頂点の一つからDFSし、指定頂点がないsubtreeを切り落としておこう。
すると、単に残ったグラフの全頂点を通る最短経路を求める問題となる。
ある点から初めて全部たどる、だと難しいので、全部の辺を辿って元の位置に戻る閉路を考え、そこから最遠の2点間の移動を間引くことにする。
閉路長は残った辺の数の2倍なので、後は最遠の2点をDFS2回で求めていこう。
1回目で各点から葉までの最長距離を求め、2回目で親側の最長距離を求めればよい。
int N,M,P; vector<int> E[200000]; int man[202020]; vector<pair<int,int> > V; int cd; int st; vector<pair<int,int>> D[202020]; int ma=0,cand=0; int dfs(int cur,int pre) { FORR(r,E[cur]) if(r!=pre) D[cur].push_back({dfs(r,cur),r}); D[cur].push_back({0,cur}); return max_element(ALL(D[cur]))->first+1; } void dfs2(int cur,int pre,int par) { if(pre>=0) D[cur].push_back({par,pre}); sort(ALL(D[cur])); reverse(ALL(D[cur])); int i; if(D[cur][0].first>ma || (D[cur][0].first==ma && cur<cand)) ma=D[cur][0].first,cand=cur; FORR(r,E[cur]) if(r!=pre) dfs2(r,cur,D[cur][(D[cur][0].second==r)].first+1); return; } int prune(int cur,int pre) { int num=0; vector<int> nn; FORR(r,E[cur]) if(r!=pre) { int n=prune(r,cur); num+=n; if(n) nn.push_back(r); } E[cur]=nn; if(man[cur]) st=cur; if((man[cur] || E[cur].size()) && pre>=0) E[cur].push_back(pre); return num+man[cur]; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N-1) { cin>>x>>y; E[x].push_back(y); E[y].push_back(x); } FOR(i,M) { cin>>x; man[x]=1; st=x; } if(M==1) return _P("%d\n%d\n",st,0); prune(st,-1); int p=st; prune(st,-1); FOR(i,N) FORR(r,E[i+1]) P++; dfs(p,-1); dfs2(p,-1,0); _P("%d\n%d\n",cand,P-ma); }
まとめ
割と雑に書いたけど本番通ってよかった。