BZOJ 1758 重建计划

发表于 | 更新于

Link

被POI的智商题虐惨了，写几道数据结构颐养身心

Solution

就是普普通通的一个套了二分的点分治。 然而大部分人的做法都被hack了。 考虑一道最典型的点分治：楼教主男人八题Tree 我写的做法是在每层点分治，对每个子树双指针+归并。 极端情况：一个点，一个子树有n2\dfrac n2个点，剩下的是n2−1\dfrac n2-1个一个点的子树。而且，链上点的权值都比剩下的一堆点小。那么归并的总复杂度就是O(n24)O(\dfrac {n^2}4)。所以，这种依赖于线性扫描的点分治，一定要先把子节点按照大小/深度排序。

Code

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include "lucida"
using std::max;
using std::min;
using std::fill;
using std::sort;
const int MAXN=100000+11;
const double eps=1e-4,inf=1e11;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(){}
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre){}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
}*G[MAXN];
int deg[MAXN];
void Adde(int f,int t,int v)
{
	deg[f]++,deg[t]++;
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
int lbd,ubd,n;
double ratio;
namespace _DC_ {
	int sz[MAXN],dist[MAXN],tol,f[MAXN];
	bool ud[MAXN];
	double amx[MAXN],smx[MAXN];
	int alen,slen;
	void GetSize(int pos,int fa) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				GetSize(u,pos);
				sz[pos]+=sz[u];
			}
	}
	int DP(int pos,int fa) {
		int mxsize=0,res=0;
		f[pos]=tol-sz[pos];
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				int temp=DP(u,pos);
				res=(res==0 || f[res]>f[temp])?temp:res;
				chkmx(mxsize,sz[u]);
			}
		chkmx(f[pos],mxsize);
		return (res==0 || f[res]>f[pos])?pos:res;
	}
	int GC(int pos) {
		tol=sz[pos];
		return tol<lbd?-1:DP(pos,0);
	}
	bool Calc() {
		for(int i=lbd,endi=min(ubd,slen);i<=endi;++i)
			if(smx[i]>=0) return 1;
		static int Q[MAXN],he,ta;
		he=1,ta=0;
		//枚举在左边取长度为i的部分
		//右边取[lbd-i,min(ubd-i,slen)]
		for(int i=min(alen,ubd-1),p=0;i>=1 && lbd<=slen+i;--i) {
			while(p+1<=min(ubd-i,slen)) { 
				++p;
				while(he<=ta && smx[p]>smx[Q[ta]])
					ta--;
				Q[++ta]=p;
			}
			while(Q[he]<lbd-i)	
				he++,assert(he<=ta);
			if(amx[i]+smx[Q[he]]>=0)
				return 1;
		}
		for(int i=1;i<=slen;++i) {
			amx[i]=i>alen?-inf:amx[i];
			chkmx(amx[i],smx[i]);
			smx[i]=-inf;
		}
		chkmx(alen,slen);
		return 0;
	}
	int DFS(int pos,int fa,int dep,double sumv,double ratio) {
		smx[dep]=chkmx(slen,dep)?-inf:smx[dep];
		chkmx(smx[dep],sumv);
		int dist=dep;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				chkmx(dist,DFS(u,pos,dep+1,e->v-ratio+sumv,ratio));
			}
		return dist;
	}
	int Go(int pos,int fa) {
		dist[pos]=0;
		sz[pos]=1;
		int res=0;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa && !ud[e->to]) {
				int u=e->to;
				chkmx(res,max(e->v,Go(u,pos)));
				chkmx(dist[pos],dist[u]);
				sz[pos]+=sz[u];
			}
		++dist[pos];
		return res;
	}
	bool cmpDist(const int &x,const int &y) {
		return dist[x]<dist[y];
	}
	double DC(int pos,double preAns) {
		pos=GC(pos);
		if(pos==-1)
			return 0;
		ud[pos]=1;
		
		static int son[MAXN],vtf[MAXN];
		int sc=0;
		double L=preAns,R=0;
		for(Edge *e=G[pos];e;e=e->pre)
			if(!ud[e->to]) {
				chkmx(R,(double)max(e->v,Go(son[++sc]=e->to,0)));
				vtf[e->to]=e->v;
			}
		sort(son+1,son+1+sc,cmpDist);
		while(R-L>eps) {
			bool tak=0;
			double Mid=(L+R)/2;
			alen=slen=0;
			for(int i=1;i<=sc;++i) {
				int u=son[i];
				slen=DFS(u,0,1,vtf[u]-Mid,Mid);
				if(Calc()) {
					tak=1;
					break;
				}
			}
			if(tak)
				L=Mid;
			else
				R=Mid;
		}
		double res=L;
		for(Edge *e=G[pos];e;e=e->pre)
			if(!ud[e->to])
				chkmx(res,DC(e->to,res));
		return res;
	}
}
using namespace _DC_;
int main() {
//	freopen("input","r",stdin);
	is>>n;
	int maxv=0;is>>lbd>>ubd;
	for(int i=1;i<=n-1;++i) {
		int a,b,v;
		is>>a>>b>>v;
		Adde(a,b,v);
		chkmx(maxv,v);
	}
	GetSize(1,0);
	double Ans=DC(1,0);
	printf("%.3lf\n",Ans);
	return 0;
}