给定一棵n个点的树,每条边有权值。
求一条链，这条链包含的边数在L和U之间，且平均边权最大。
类似于分数规划问题，转换为二分答案
将每条边减去二分值，判断是否有权值和大于等于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
using namespace std;
int head[100005],vet[200005],nxt[200005],w[200005],num;
bool vis[100005];
int sz[100005],mxs[100005],root,sz1,sz2;
int que[100005];
double mxr,ans,mid,d1[100005],d2[100005];
int L,U,n;
inline int read() {
char ch=0;int sum=0;
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
return sum;
}
inline void addedge(int x,int y,int c) {
num++;vet[num]=y;nxt[num]=head[x];w[num]=c;head[x]=num;
num++;vet[num]=x;nxt[num]=head[y];w[num]=c;head[y]=num;
}
void getdepth(int x,int ff,int dep,double sum) {
if (dep>sz2) {
sz2=dep;
d2[dep]=-1e11;
}
d2[dep]=max(d2[dep],sum);
for (int e=head[x];e;e=nxt[e]) {
if (vet[e]==ff||vis[vet[e]]) continue;
getdepth(vet[e],x,dep+1,sum+w[e]-mid);
}
}
inline double calc() {
int h=1,t=0;
int i=min(U,sz2),j=0;
double mx=-1e11;
for (;i;i--) {
while (j<=sz1&&i+j<=U) {
while (h<=t&&d1[que[t]]<=d1[j]) t--;
que[++t]=j;
j++;
}
while (h<=t&&que[h]+i<L) h++;
if (h>t) return mx;
mx=max(mx,d1[que[h]]+d2[i]);
if (mx>=0) return mx;
}
return mx;
}
inline bool check(int x) {
sz1=sz2=0;
for (int e=head[x];e;e=nxt[e]) {
int v=vet[e];
if (vis[v]) continue;
getdepth(v,x,1,w[e]-mid);
if (calc()>=0) return true;
for (int i=1;i<=sz2;i++) {
if (i>sz1) d1[i]=-1e11;
d1[i]=max(d1[i],d2[i]);
d2[i]=-1e11;
}
sz1=max(sz1,sz2);
sz2=0;
}
return false;
}
void bs(int x) {
double l=ans,r=mxr;
while (r-l>=0.0001) {
mid=(l+r)/2;
if (check(x)) l=mid;
else r=mid;
}
ans=max(ans,l);
}
void getroot(int x,int ff,int tt) {
sz[x]=1;mxs[x]=0;
for (int e=head[x];e;e=nxt[e]) {
int v=vet[e];
if (vis[v]||v==ff) continue;
getroot(v,x,tt);
sz[x]+=sz[v];
mxs[x]=max(mxs[x],sz[v]);
}
mxs[x]=max(mxs[x],tt-sz[x]);
if (mxs[root]>mxs[x]) root=x;
}
void solve(int x,int tot) {
bs(x);
vis[x]=1;
for (int e=head[x];e;e=nxt[e]) {
if (vis[vet[e]]) continue;
int tt=sz[vet[e]];root=0;
if (tt>sz[x]) tt=tot-sz[x];
getroot(vet[e],x,tt);
solve(root,tt);
}
}
int main() {
n=read();L=read();U=read();
for (int i=1;i<n;i++) {
int x=read(),y=read(),c=read();
addedge(x,y,c);
mxr=max(mxr,(double)c);
}
for (int i=1;i<=n;i++) d1[i]=d2[i]=-1e11;
mxs[0]=1e9;
getroot(1,0,n);
solve(root,n);
printf("%.3lf",ans);
return 0;
}
蒟蒻用dfs算距离
dalao用bfs算距离
http://hzwer.com/5362.html
蒟蒻的常数肯定比dalao大 orz