「CF1039D」You Are Given a Tree

传送门

Luogu

解题思路

整体二分。

的确是很难看出来，但是你可以发现输出的答案都是一些可以被看作是关键字处于 \([1, n]\) 的询问，而答案的范围又很显然是 \([0, n]\)，这不就刚好满足了整体二分的几个组成部分了吗。　　

那么我们要如何求出 \(mid\) 位置的解呢？　　

考虑 \(\text{DP}\)

我们很显然可以将子树中的点尽可能合并后再向父亲传递，所以我们对每一次DP的根节点分别记一个子树中的最大值，和一个非严格次大值，然后我们尝试合并这两个值，要是合并不了，就给答案加一，不然就把最大值上传。

正确性和NOIP2018赛道修建有异曲同工之妙

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

const int _ = 100000 + 2;

int tot, head[_], nxt[_ << 1], ver[_ << 1];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, ans[_], dp[_];

inline void dfs(int u, int f, int x) {

	dp[u] = 0;

	int mx = 0, mn = 0;

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		dfs(v, u, x);

		if (dp[v] > mx) mn = mx, mx = dp[v];

		else mn = max(mn, dp[v]);

	}

	if (mx + mn + 1 >= x) dp[u] = 0, ++ans[x];

	else dp[u] = mx + 1;

}

inline void binary(int l, int r, int L, int R) {

	if (l > r || L > R) return ;

	if (L == R) {

		for (rg int i = l; i <= r; ++i) ans[i] = L; return ;

	}

	int mid = (l + r) >> 1;

	ans[mid] = 0, dfs(1, 0, mid);

	binary(l, mid - 1, ans[mid], R);

	binary(mid + 1, r, L, ans[mid]);

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int u, v, i = 1; i < n; ++i)

		read(u), read(v), Add_edge(u, v), Add_edge(v, u);

	binary(1, n, 0, n);

	for (rg int i = 1; i <= n; ++i) printf("%d\n", ans[i]);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF1039D」You Are Given a Tree

解题思路

细节注意事项

参考代码

最新文章

热门文章