「SOL」重建计划(BZOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」重建计划(BZOJ)

发表于 分类于 Valine：

期末考完上竞赛，新春佳节上竞赛，元宵大年上竞赛，开学继续上竞赛
╰（‵□′）╯

# 题面

给定一棵 $n$ 个点的边带权的树，要求选出一条边的数量在 $L,R$ 之间的简单路径，使得该路径的边权平均值最大。求该最大平均值。

数据规模：$n\le10^5$，边权不超过 $10^6$。

# 解析

平均值问题，不难想到分数规划。于是首先二分出答案，然后给每个边权减去二分值，问题转化为「找出一条边的数量在 $L,R$ 之间，边权和大于等于 $0$ 的简单路径」。这样的话，其实就相当于求边权和最大的路径，判断其边权是否大于等于 $0$。

树上的路径问题，于是可以想到树分治。不能边分治，因为边分治需要改变树形，重构出的树的路径的边权平均值和原树是不一样的。只能考虑点分治。

那么就是要统计过重心的路径。考虑依次（可以先想一下依什么次）遍历子树，统计出已经遍历的子树中「到重心边数为 $i$ 的路径的最大权」记为 $f_i$。为了避免算到两个端点在同一棵子树中的路径（非简单路径），我们要先用计入子树 $v$ 之前的 $f_i$ 与子树 $v$ 来计算答案后，再将子树 $v$ 合并到 $f_i$ 中。

怎么计算答案？我们按路径长度从小到大枚举子树 $v$ 的一条路径，不妨记该路径长度为 $i$，那么另一条路径长度范围 $[L-i,R-i]$。随着 $i$ 增大，这个区间是只会往左移动的，而我们要求的就是这个区间中 $f_i$ 的最大值，这个问题可以用单调队列解决。

现在来分析一下时间复杂度，记当前分治的连通块大小为 $S$，$f_i$ 的长度是 $O(S)$ 的，那么每求一次答案需要将 $f_i$ 扫一遍，所以复杂度是 $O(S^2)$ 的？？？这与点分治要求的每个连通块内的复杂度 $O(S)$ 差得也太多了。

不难想到，在将子树 $v$ 的信息合并到 $f_i$ 的过程中，$f_i$ 的长度是不断增大的，所以 $f_i$ 扫描的起点不从 $S$ 开始，而是从当前有值的位置开始。

但是这样仍然不足够——如果我们遍历的第一棵子树是所有子树中最大的一棵（最大有 $\frac{S}{2}$，因为是点分治嘛）那么合并信息后 $f_i$ 的长度直接就变成了 $O(S)$，之后每棵子树都要扫一遍 $f_i$，复杂度还是 $O(S^2)$ 的。

所以注意到之前的那个问题「按什么顺序遍历子树？」我们可以聪明一点，先从深度小的开始遍历，类似于启发式的思想（不知道算不算启发式）。再分析复杂度，在计算某一棵子树的答案时，$f_i$ 的长度是上一棵子树的深度。总的遍历的复杂度是所有子树深度之和，于是就保证了复杂度是 $O(S)$ 的。

于是最终复杂度 $O(n\log n\log w)$（$w$ 是二分的权值范围）。

# 源代码

点击展开/折叠代码 
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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=1e5+10;
#define con(type) const type &
const double EPS=1e-8;
typedef pair<int,int> pii;

struct SuperDeque{
	int ary[N],le,ri;
	void clear(){le=1,ri=0;}
	void push_back(con(int)x){ary[++ri]=x;}
	void pop_back(){ri--;}
	void pop_front(){le++;}
	int back(){return ary[ri];}
	int front(){return ary[le];}
	int size(){return ri-le+1;}
}que;

int n,bonl,bonr,rsiz,rwei,rroot;
int siz[N],hgt[N];
double val_bas;
double val_bin[N],tmp_bin[N];
bool ban[N],ifsort[N];
vector<pii> lnk[N];

int findCenter(con(int)u,con(int)fa){
	int maxsizv=0,sizu=1;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		int sizv=findCenter(v,u);
		maxsizv=max(maxsizv,sizv);
		sizu+=sizv;
	}
	int weiu=max(rsiz-sizu,maxsizv);
	if(weiu<rwei) rwei=weiu,rroot=u;
	return sizu;
}
int dataDFS(con(int)u,con(int)fa,con(double)val,con(int)dep){
	int ret=0;
	siz[u]=1;
	tmp_bin[dep]=max(tmp_bin[dep],val);
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		ret=max(ret,dataDFS(v,u,val+lnk[u][it].second-val_bas,dep+1));
		siz[u]+=siz[v];
	}
	return ret+1;
}
int highDFS(con(int)u,con(int)fa){
	int ret=0;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		ret=max(ret,highDFS(v,u));
	}
	return ret+1;
}
bool cmp(con(pii)a,con(pii)b){return hgt[a.first]<hgt[b.first];}
bool ina_abs(con(double)key){return key<0?-key:key;}
int sgn(con(double)key){return ina_abs(key)<EPS?0:(key<0?-1:1);}
bool dacDFS(int u,con(int)totsiz){
	ban[u]=true;
	if(!ifsort[u]){
		for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
			int v=lnk[u][it].first;
			if(ban[v]) continue;
			hgt[v]=highDFS(v,u);
		}
		sort(lnk[u].begin(),lnk[u].end(),cmp);
		ifsort[u]=true;
	}
	fill(val_bin,val_bin+totsiz+1,-1e9),val_bin[0]=0;
	int ardlen=0;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(ban[v]) continue;
		int hgtv=dataDFS(v,0,lnk[u][it].second-val_bas,1);
		que.clear();
		for(int i=1,j=ardlen;i<=hgtv;i++){
			while(j>=bonl-i && j>=0){
				while(que.size() && sgn(val_bin[que.back()]-val_bin[j])<=0)
					que.pop_back();
				que.push_back(j);
				j--;
			}
			while(que.size() && que.front()>bonr-i) que.pop_front();
			if(que.size() && sgn(val_bin[que.front()]+tmp_bin[i])>=0)
				return true;
		}
		for(int i=1;i<=hgtv;i++){
			val_bin[i]=max(val_bin[i],tmp_bin[i]);
			tmp_bin[i]=-1e9;
		}
		ardlen=hgtv;
	}
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(ban[v]) continue;
		rwei=1e9,rsiz=siz[v];
		findCenter(v,0);
		if(dacDFS(rroot,siz[v])) return true;
	}
	return false;
}
bool check(con(double)mmi){
	fill(tmp_bin,tmp_bin+1+n,-1e9);
	for(int i=1;i<=n;i++) ban[i]=false;
	val_bas=mmi;
	rsiz=n,rwei=1e9,findCenter(1,0);
	return dacDFS(rroot,n);
}
int main(){
	rin(n),rin(bonl),rin(bonr);
	for(int i=1,u,v,l;i<n;i++){
		rin(u),rin(v),rin(l);
		lnk[u].emplace_back(v,l);
		lnk[v].emplace_back(u,l);
	}
	double lle=0,rri=1e6,mmi;
	while(lle+1e-4<rri){
		mmi=(lle+rri)/2;
		if(check(mmi)) lle=val_bas;
		else rri=val_bas;
	}
	printf("%.3f\n",lle);
	return 0;
}

THE END

Thanks for reading!

进退之间觉醒 逆转之力
被黑暗俘虏 想让我沉溺
绝不会认输 信己不信命
崩坏的秩序 打破既定的结局

——《陷落之序》By 著小生zoki

> Link 陷落之序-Bilibili