【CEOI2022】Drawing（全局平衡二叉树，构造，分治）

题面

题解

我们可以给出一个 $O(N^2)$ 的构造方法证明一定有解：随便定一个树根，递归解决问题，令当前根为 $u$ ，坐标集合为 $S$ ，在 $S$ 中已经确定一个坐标点 $U$ 对应 $u$。以 $U$ 为中心，对剩下的坐标进行极角排序，排序后按照 $u$ 的子树大小切割成连续段 $S_1,S_2,...$ 并分配给 $u$ 的每个子树 $v_1,v_2,...$，每个 $v_i$ 的根对应 $S_i$ 极角排序中最靠前的坐标，然后递归下去。所有 $S_i$ 的凸包两两之间都是不相交的，方案一定合法。用 nth_element 代替极其浪费的 sort ，可以做到 $O(N^2)$ 。

如果给出的是一棵平衡的树的话，复杂度就可以降为 $O(n\log n)$ 。可惜不满足。

---

我们能否用一些特殊分治操作让它同样达到 $O(n\mathrm{poly}(\log n))$ 呢？比如点分治？边分治？（好巧，题目已经给三度化了）

还是会有很大的问题，比如点分，我们无法保证当前分治的连通块的决策不与外面已经决策好的点冲突。根本问题是，点分和边分的连通块都是由很多个点来划分边界的，边界点对当前块的决策干扰很大。

---

那我们能否找到用三个点甚至两个点划分边界的方法呢？(并非homo)

从字面上看其实挺好办，任意两个点割开，确实可以划分出一个连通块，接下来只需要想办法让每次分治规模减半。

---

试试用直径？先找到整棵树的直径，两个分治中心 $x,y$（划分边界的，可以这么说吧？）定为直径两端、并分配凸包上相邻两点 $A,B$ 后开始分治。找到 $x,y$ 中点 $m$ ，令 $[x,m)$ 表示的连通块为删掉 $m$ 后与 $x$ 联通的点集∪{点 $m$} ，$[m,y)$ 表示删掉 $m$ 后与 $x$ 不连通的点集∪{点 $m$}。然后找到坐标凸包边界上的一个三角形 $ABC$ 如下图：

满足 $O\cup P$ 的大小不小于 $[x,m)$ 的点数，$P\cup Q$ 的大小不小于 $[m,y)$ 的点数，且关键是 $\Delta ABC$ 内部不能有其它点。

把 $m$ 对应点设为 $C$ ，以 $C$ 为中心点对剩下的点极角排序，然后根据点数分成左右两半给 $[x,m)$ 和 $[m,y)$ ，分治下去。每当 $x$ 与 $y$ 相邻的时候，说明 $y$ 在此连通块内除了 $x$ 以外没有邻接点了，那么在连通块内找一个与 $x$ 距离最远的点把它当作 $y$ ，然后分配一个 $x$ 在凸包上的相邻点给 $y$ 就好。

但是很可惜，用长链剖分的思路可以证明这个方法是 $O(n\sqrt{n\log n})$ 的。

剖分？我们可以试试换成重链剖分！把“直径”和“最远点”改成重链剖分下的重链端点，那么可以证明复杂度是 $O(n{\log }^{2}n)$ 的，有点紧。

其实到这里我们发现 $m$ 没必要一定选择中点，更好的选择是加权中点，即尽量保证 $[x,m)$ 和 $[m,y)$ 的大小相近。这就是全局平衡二叉树分治了，刚好用上了三度化的条件。时间复杂度为 $O(n\log n)$ ，如果偷懒用 sort 的话就是 $O(n{\log }^{2}n)$ 。

CODE

我是懒狗

#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma GCC optimize(2)
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned LL
#define DB double
#define lowbit(x) (-(x)&(x))
#define ENDL putchar('\n')
#define FI first
#define SE second
#define PR pair<int,int>
inline int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos=0,len=fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
	LL f=1,x=0;int s=getchar();
	while(s<'0'||s>'9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
	while(s>='0'&&s<='9') {x = (x<<3)+(x<<1)+(s^48);s=getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x=-x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],cne;
void ins(int x,int y) {
	nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
bool f[MAXN];
int siz[MAXN],SIZ,son[MAXN],sz2[MAXN];
void dfs(int x,int ff) {
	siz[x] = 1; son[x] = 0;
	for(int i = hd[x];i;i = nx[i]) {
		if(v[i] != ff && !f[v[i]]) {
			dfs(v[i],x);
			siz[x] += siz[v[i]];
			if(siz[v[i]] > siz[son[x]]) son[x] = v[i];
		}
	}
	sz2[x] = siz[x] - siz[son[x]];
	return ;
}
struct it{
	int x,y,i;
}a[MAXN],RT,as[MAXN];
inline PR operator - (it a,it b) {return {a.x-b.x,a.y-b.y};}
bool cmp(it a,it b) {
	PR A = a-RT,B = b-RT;
	return A.FI*1ll*B.SE - A.SE*1ll*B.FI > 0;
}
void solve(int x,int y,int l,int r) {
	if(l > r) return ;
	RT = as[x];
	sort(a + l,a + r + 1,cmp);
	if(x == y) {
		dfs(x,0);
		while(son[y]) y = son[y];
		as[y] = a[r]; r --; f[y] = 1;
	}
	int md = x;
	while(son[md] && son[md] != y && siz[md] >= (siz[x]+siz[y])/2) md = son[md];
	if(md == x) {
		int le = sz2[x]-1;
		solve(x,x,l,l+le-1);
		solve(y,y,l+le,r);
		return ;
	}
	int l1 = siz[x] - siz[md] - 1;
	RT = as[y]; int ps = l+l1;
	for(int i = l+l1;i <= r;i ++) if(cmp(a[i],a[ps])) ps = i;
	swap(a[l+l1],a[ps]); as[md] = a[l+l1]; f[md] = 1;
	solve(x,md,l,l+l1-1); solve(md,y,l+l1+1,r);
	return ;
}
int main() {
	// freopen("drawing.in","r",stdin);
	// freopen("drawing.out","w",stdout);
	n = read();
	for(int i = 1;i < n;i ++) {
		s = read();o = read();
		ins(s,o); ins(o,s);
	}
	for(int i = 1;i <= n;i ++) {
		a[i].x = read();
		a[i].y = read();
		a[i].i = i;
	}
	int p = 1;
	for(int i = 2;i <= n;i ++) {
		if(a[i].y > a[p].y) p = i;
	}
	swap(a[p],a[1]); f[1] = 1; as[1] = a[1];
	solve(1,1,2,n);
	for(int i = 1;i <= n;i ++) {
		AIput(as[i].i,i==n ? '\n':' ');
	}
	return 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
114
115
116
117
118