CODE FESTIVAL 2016 Relay K - 木の問題

解法

次数が $3$ 以上の頂点は取り除いても、最適解を構成できる。
次数が $3$ の頂点は、たかだか $2$ 個の部分木しか繋げられないので、 $1$ つ以上の部分木が余る。
そのため、次数が $3$ 以上の頂点が最適解に含まれる時、その部分木の中の次数が $1$ の頂点と交換してあげれば、同じ長さの最適解を構成できる。

次数が $1$ の頂点は最適解に必ず含まれる。
これは、最適解が次数 $1, 2$ の頂点しか含んでいないことと、次数 $3$ の頂点を消去した時にできる部分木 $T$ の中に、最適解になる頂点が $1$ つ以上存在するということを考えると、
その頂点を葉に移動させてあげれば良いので、これも良い。

次数が $3$ のものを消して、次数が $1$ の最適解を採用すると、木の中の任意の頂点 $u, v$ の最短経路の中に含まれる次数が $2$ の頂点のみを含めることが出来る。
そのため、一番次数が $2$ の頂点を多く含むパスを採用することで、最大の集合 $M$ を見つけることが出来る。

次数が $1$ のものを数える
次数が $2$ のものを一番多く含むものを計算する->適当なところから木DP $O(N)$

全体の計算量は $O(N)$

Source

int main() {
	int N; cin >> N;
	vvint G(N);	
	for (int i = 0; i < N-1; i++) {
		int p, q;
		cin >> p >> q; --p, --q;
		G[p].push_back(q);
		G[q].push_back(p);
	}
	
	int maxd = 0;
	function<int(int, int)> dfs = [&](int u, int prev) {
		int ret = (int)(G[u].size() == 2);
		vint dat;
		for (auto &v : G[u]) {
			if (v != prev) dat.push_back(dfs(v, u));
		}

		sort(begin(dat), end(dat), greater<>());
		int maxv = 0;
		if (dat.size() >= 1) {
			maxv = dat[0];
			if (dat.size() >= 2) chmax(maxd, dat[0] + dat[1]);
		}
		chmax(maxd, ret + maxv);
		return (ret + maxv);
	};

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (G[i].size() == 1) cnt++;
	}
	dfs(i, -1);
	cout << cnt + maxd << endl;
	return (0);
}