NKOJ 3984 （WC 2010）重建计划（二分答案+点分治+单调dp）

发表于 |
字数统计: 1,364字 | 阅读时长 ≈ 7min

P3984[WC2010]重建计划

问题描述

这里写图片描述

输入格式

第一行包含一个正整数N，表示X国的城市个数.
第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限
接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

输出格式

输出最大平均估值，保留三位小数

样例输入 1

4
2 3
1 2 1
1 3 2
1 4 3

样例输出 1

2.500

样例输入 2

12
3 5
1 2 804224
1 3 645617
2 4 763931
2 6 744133
2 8 534824
4 5 163318
6 7 421158
6 10 773167
6 11 380598
8 9 639836
9 12 261707

样例输出 2

773841.333

提示

20%的数据,N<=5000
30%的数据,N<=100000,原有方案恰好为一条路径
100%的数据,N<=100000,1<=L<=U<=N-1,Vi<=1000000

题目中要求的东西带了个平均值，不好处理，考虑二分答案，然后将每条边权减去mid，那么原题变成求是否存在一条长度在$[L,R]$之间，且权值和$>=0$的路径。

树上路径问题，考虑点分治，考虑过分治中心的路径，按子树顺序讨论，记录$F[d]$表示当前子树之前的子树深度为$d$的最大路径的权，$G[d]$表示当前子树深度为$d$的路径的最大权，那么可以dp，从小到大枚举d，用$G[d]$与$F[L-d]-F[R-d]$来更新答案，显然可以用单调队列来优化。dp完了之后用$G$更新$F$，继续讨论下一棵子树。

这里理论上需要将子树按照最大深度排序来保证复杂度。具体不好说。

另外需要加上一些剪枝，即当前子树点数小于L就不用分治下去了。
另外，最好每层点分治单独二分，这样会跑得比较快。
但是我就是在外面二分，这样就需要加上一些其他优化才能卡过了，比如找到答案就不继续分治，预处理点分治树而不要每次都重新建立点分治树之类。

总时间复杂度$O(n\log^2n)$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
#define N 200005
using namespace std;
deque<int>Q;
double Lim;
int n,L,R;
int TOT,LA[N],NE[N],EN[N];
double LE[N],F[2][N];
int Min,rt,Rt,si[N],Md;
bool mark[N];
vector<int>to[N],son[N];
void ADD(int x,int y,double z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Gsi(int x,int f)
{
	int i,y;si[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y]||y==f)continue;
		Gsi(y,x);si[x]+=si[y];
	}
}
void Grt(int x,int s,int f)
{
	int i,y,Max=0;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y==f||mark[y])continue;
		Grt(y,s,x);
		if(si[y]>Max)Max=si[y];
	}
	if(s-si[x]>Max)Max=s-si[x];
	if(Max<Min)Min=Max,rt=x;
}
void Gdis(int x,double s,int d,int f,int ty)
{
	if(d>R)return;
	F[ty][d]=max(F[ty][d],s);Md=max(Md,d);
	for(int i=LA[x];i;i=NE[i])
	if(EN[i]!=f&&!mark[EN[i]])Gdis(EN[i],s+LE[i]-Lim,d+1,x,ty);
}
bool MT(int a,int b)
{
	int i,j,l=a;
	Q.clear();
	for(i=1;i<=b;i++)
	{
		while(l>=0&&i+l>=L)
		{
			while(Q.size()&&F[0][Q.back()]<=F[0][l])Q.pop_back();
			Q.push_back(l);l--;
		}
		while(Q.size()&&i+Q.front()>R)Q.pop_front();
		if(Q.size()&&F[1][i]+F[0][Q.front()]>=0)return 1;
	}
	return 0;
}
void PreDC(int x)
{
	int i,y;mark[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y])continue;
		Min=1e9;Gsi(y,0);Grt(y,si[y],0);
		si[rt]=si[y];
		to[x].push_back(rt);
		PreDC(rt);
	}
}
bool DC(int x)
{
	int i,j,y,las;las=Md=0;mark[x]=1;
	if(si[x]<L)return 0;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y])continue;
		las=max(las,Md);Md=0;
		Gdis(y,LE[i]-Lim,1,x,1);
		if(MT(las,Md))return Md=max(Md,las),1;
		Gdis(y,LE[i]-Lim,1,x,0);
		for(j=0;j<=Md;j++)F[1][j]=-1e9;
	}
	for(i=1;i<=las||i<=Md;i++)F[0][i]=-1e9;
	for(i=0;i<to[x].size();i++)
	{
		y=to[x][i];
		if(DC(y))return 1;
	}
	return 0;
}
bool ok(double mid)
{
	Lim=mid;
	if(!Md)Md=1e5;
	memset(mark,0,sizeof(mark));
	for(int i=1;i<=Md;i++)F[0][i]=F[1][i]=-1e9;
	if(DC(Rt))return 1;
	return 0;
}
void EF(double l,double r)
{
	double mid;
	while(r-l>=0.0001)
	{
		mid=(l+r)/2;
		if(ok(mid))l=mid;
		else r=mid;
	}
	printf("%.3lf",(l+r)/2);
}
int main_main()
{
	int i,j,k,x,y,z,Max=0;
	scanf("%d%d%d",&n,&L,&R);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,1.0*z);ADD(y,x,1.0*z);Max=max(Max,z);
	}
	Min=1e9;Gsi(1,0);Grt(1,n,0);
	si[rt]=n;Rt=rt;PreDC(rt);
	EF(double(0),double(Max));
}
const int main_stack=16;
char my_stack[128<<20];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp"); 
  return 0;
}