Loj 3265 Delegation

Posted on | Views:

[NOIP 2018] 赛道修建 再放送.

虽说是再放送,但是在处理细节上还是有一点区别的.

二分答案,考虑检查每条路径长度都 $\ge k$ 是否可行.

在点 $x$ 的时候,需要合并从每个儿子传上来的每条路径,并且传最多一条路径上去.

在保证其余路径能被合法合并的前提下,传上去的路径长度应当尽可能大,二分这个值,检查其余路径能否匹配即可.

注意在根节点处不能再传路径上去,即只能检查传上去的路径长度为 $0$ 是否合法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e5 + 10;
int n;
vector<int> G[N], a[N];
int t[N], b[N];
int solve1(int x, int m, int k)
{
	for (int i = 1; i <= m; ++i)
		t[i] = a[x][i];
	if (m & 1)
		t[++m] = 0;
	sort(t + 1, t + 1 + m);
	for (int i = 1; i < m + 1 - i; ++i)
		if (t[i] + t[m + 1 - i] < k)
			return -1;
	return 0;
}
int solve2(int x, int m, int k)
{
	for (int i = 1; i <= m; ++i)
		t[i] = a[x][i];
	if (!(m & 1))
		t[++m] = 0;
	sort(t + 1, t + 1 + m);
	int L = 1, R = m, s = -1;
	while (L <= R)
	{
		int mid = (L + R) >> 1, f = 1;
		for (int i = 1; i <= m; ++i)
			if (i < mid)
				b[i] = t[i];
			else if (i > mid)
				b[i - 1] = t[i];
		for (int i = 1; i < m - i && f; ++i)
			if (b[i] + b[m - i] < k)
				f = 0;
		if (f)
			s = t[mid], L = mid + 1;
		else
			R = mid - 1;
	}
	return s;
}
int dfs(int x, int F, int k)
{
	int m = 0;
	a[x].clear(), a[x].push_back(0);
	for (int y : G[x])
		if (y != F)
		{
			++m;
			int len = dfs(y, x, k);
			if (len == -1)
				return -1;
			a[x].push_back(len + 1);	
		}
	if (x != 1)
	{
		int p = solve2(x, m, k);
		if (p != -1)
			return p;
	}
	return solve1(x, m, k);
}
int main()
{
	n = read();
	for (int i = 1; i < n; ++i)
	{
		int u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int L = 1, R = n - 1, ans = 0;
	while (L <= R)
	{
		int mid = (L + R) >> 1;
		if (dfs(1, 0, mid) != -1)
			ans = mid, L = mid + 1;
		else
			R = mid - 1;
	}
	write(ans, '\n');
	return 0;
}