JOISC D3T3 Meeting 2

每天只挑最简单的做就是我了

称有人的点为关键点。

首先观察样例会发现,如果关键点的个数为奇数,答案肯定是 $1$ 。我们设任意一个开会地点为 $u$ ,那么显然有所有儿子子树内的关键点个数不超过一半,而又是奇数,往任何一个方向走肯定都无法使得答案保持不变,而且一定是变得不优。同时如果你一直往某个方向走,原本子树大小不超过一半之后也一定不超过,所以一定会越来越不优。

类似的思路,考虑偶数的时候,如果存在多解,肯定是找到了一个点,使得所有点被平均分配到两个子树里面,这样就可以把根向这两个子树移动,如果不是这样分配的,显然也走不动。

因此可以发现,最优解肯定是找到一条路径,使得这条路径的两端的非路径方向的子树大小都 $\ge k$ ,且这条路径尽可能长。我们先不考虑垂直的路径,一种简单的做法是按照子树 $siz$ 从大到小加点,维护当前连通块直径即可。但是这样无法处理到垂直的路径,会发现垂直路径会非常难搞。如果考虑点分,想一下会发现怎么也是两个 $\log$ 的。

如果提重心作为根,会发现一个非常牛逼的性质,就是对于一个路径,它的两端的非路径方向子树大小最小值必然是两端在重心为根的时候的子树大小最小值。考虑证明非常简单,如果两个点非垂直路径显然成立,如果是垂直路径,由于重心做根,所以祖先点的非路径方向 $siz$ 大小显然是大于 $\frac n 2$ 的,这肯定没有子孙点优秀,同时祖先点的路径方向大小也是大于子孙点的,所以也可以直接取两个子树大小的最小值。

于是就加点,加点,加点,维护直径,就做完了。复杂度 $O(n\log n)$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
vi G[MAXN];

int siz[MAXN] , idx[MAXN];
int ps;
void dfs( int u , int f ) {
siz[u] = 1;
int mx = 0;
for( int v : G[u] ) if( v != f ) dfs( v , u ) , siz[u] += siz[v] , mx = max( mx , siz[v] );
mx = max( mx , n - siz[u] );
if( mx <= n / 2 ) ps = u;
}

int g[MAXN][20] , dep[MAXN];
void afs( int u , int f ) {
dep[u] = dep[f] + 1;
siz[u] = 1;
for( int v : G[u] ) if( v != f ) {
g[v][0] = u;
rep( k , 1 , 18 ) if( g[g[v][k-1]][k-1] )
g[v][k] = g[g[v][k-1]][k-1];
else break;
afs( v , u );
siz[u] += siz[v];
}
}

int lca( int u , int v ) {
if( dep[u] < dep[v] ) swap( u , v );
if( dep[u] != dep[v] )
for( int k = 18 ; k >= 0 ; -- k ) if( dep[g[u][k]] >= dep[v] )
u = g[u][k];
if( u == v ) return u;
for( int k = 18 ; k >= 0 ; -- k ) if( g[u][k] != g[v][k] )
u = g[u][k] , v = g[v][k];
return g[u][0];
}

int dis( int a , int b ) {
return dep[a] + dep[b] - 2 * dep[lca( a , b )] + 1;
}

tuple<int,int,int> cur;
int as[MAXN];

void solve() {
cin >> n;
rep( i , 2 , n ) {
int u , v;
scanf("%d%d",&u,&v);
G[u].pb( v ) , G[v].pb( u );
}
dfs( 1 , 1 ) , afs( ps , ps );
rep( i , 1 , n ) idx[i] = i;
sort( idx + 1 , idx + 1 + n , [&]( int a , int b ) { return siz[a] > siz[b]; } );
cur = make_tuple( 1 , ps , ps );
rep( i , 2 , n ) {
int u = idx[i] , s = siz[idx[i]] , a = get<1>( cur ) , b = get<2>( cur );
cur = max( { cur , make_tuple( dis( u , a ) , u , a ) , make_tuple( dis( u , b ) , u , b ) } );
as[s] = get<0>( cur );
}
per( i , n , 1 ) as[i] = max( as[i + 1] , as[i] );
rep( i , 1 , n ) {
printf("%d\n",( i & 1 ) ? 1 : as[i / 2] );
}
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/2021/03/28/joisc-d3t3-meeting-2/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog