AtCoder ARC #152 : F - Attraction on Tree

大まかな方針は思いついても、細かいところを詰めるのが難しい。
https://atcoder.jp/contests/arc152/tasks/arc152_f

問題

木を成すN頂点の無向グラフが与えられる。
初期状態で1番の頂点に駒がある。

以下の手順をN回行う。

• 今駒がある以外の頂点のうち、まだ選んだことない頂点を1個選ぶ。
• 駒を選んだ頂点に向け辺1つ分動かす。

駒は同じ頂点を複数回経由してもよい。
適切な順で頂点を選んだ時、駒が最後N番にいられる手順があるか。
あるのであれば、そのうち訪問する頂点数の最小値を求めよ。

解法

1番→N番のパス上の頂点は必ず通る。
それ以外に通るべき点があるかを考える。
このパスを切断すると、元のグラフはパス上の点を根とする根付き木とみなすことができる。

この各根付き木について、根頂点以外の部分に入らないといけないケースがあるかどうかを考える。
これら各点vの深さとSubTreeのサイズで決まる。SubTreeが大きいと、SubTree内の頂点を選択する回数が増えるため、vを通らないといけなくなる。
そのようなvをそれぞれ総当たりで求めよう。

int N;
vector<int> E[202020];
int D[3][202020];
int root[202020];
int C[202020];
int MD=-1,MV=-1;

void dfs(int cur,int pre,int id,int d) {
	D[id][cur]=d;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur,id,d+1);
	}
}
int dfs2(int cur,int pre,int d,int b) {
	D[2][cur]=d;
	C[cur]=1;
	FORR(e,E[cur]) if(root[e]==0&&e!=pre) {
		C[cur]+=dfs2(e,cur,d+1,b);
	}
	if(2*C[cur]>b) {
		if(d>MD) {
			MD=d;
			MV=cur;
		}
	}
	return C[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0,0,0);
	dfs(N-1,N-1,1,0);
	
	if(D[0][N-1]%2!=N%2) {
		cout<<-1<<endl;
		return;
	}
	
	FOR(i,N) if(D[0][i]+D[1][i]==D[0][N-1]) root[i]=1;
	
	FOR(i,N) if(root[i]) dfs2(i,i,0,N+D[0][i]-D[1][i]);
	
	int ret=D[0][N-1]+1;
	if(MV!=-1) {
		ret+=MD;
		vector<int> cand;
		FORR(e,E[MV]) if(D[2][e]>D[2][MV]) cand.push_back(C[e]);
		int w=0;
		sort(ALL(cand));
		reverse(ALL(cand));
		FORR(c,cand) {
			if(w<C[MV]-w-(D[0][MV]+N-C[MV]-D[1][MV])) ret++;
			w+=c;
		}
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

900ptぐらいでもいいかもしれない。