题意
分析
求这个平均值的最大值就是分数规划,二分一下就变成了求一条长度在[L,R]内路径的权值和最大.有淀粉质的做法但是我没写,感觉常数会很大.这道题可以用长链剖分做.
先对树长链剖分. 我们像做dsu on tree一样先做重儿子，用线段树继承重儿子的全部信息，然后做其他轻儿子
查询的时候枚举一下路径的长度len，一边单点查询长度为len的最大权值，一边线段树查询长度为[L-len,R-len]的区间即可
时间复杂度我不会证(后面有)…反正枚举轻儿子的深度是总共的.所以加上外面的二分,总时间复杂度为.
枚举轻儿子的深度的时间复杂度证明如下
时间复杂度。
分析如下：
每个点x只会暴力统计其所有轻儿子的信息，而每个轻儿子的信息大小为该轻儿子所在长链长度。
而当递归到x的父节点fa(x)时，若x不是fa(x)的重儿子，则fa(x)会暴力统计大小为x长链长度的信息。
故，每个长链只会对转移的复杂度做一次大小为其长度的贡献。
超强的长链剖分a!!! 证明摘自下面的博客.
学习长链剖分的看这里…博客传送门
CODE
#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; for(;!isdigit(ch=getc());)if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;
}
template<class T>inline void chkmax(T &x, T y) { if(x < y) x = y; }
const int MAXN = 100005;
const double INF = 1e16;
int n, L, R, cnt, fir[MAXN], init_len[MAXN<<1];
struct edge { int to, nxt; double w; }e[MAXN<<1];
inline void add(int u, int v, int wt) {
e[cnt] = (edge) { v, fir[u], 0 }, init_len[cnt] = wt, fir[u] = cnt++;
e[cnt] = (edge) { u, fir[v], 0 }, init_len[cnt] = wt, fir[v] = cnt++;
}
int mxd[MAXN], dep[MAXN], son[MAXN], Eson[MAXN], dfn[MAXN], tmr;
void dfs1(int u, int ff) {
mxd[u] = dep[u] = dep[ff] + 1;
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff) {
dfs1(v, u); chkmax(mxd[u], mxd[v]);
if(mxd[v] > mxd[son[u]]) son[u] = v, Eson[u] = i;
}
}
void dfs2(int u, int ff) {
dfn[u] = ++tmr;
if(son[u]) dfs2(son[u], u);
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff && v != son[u])
dfs2(v, u);
}
int num[MAXN];
double dis[MAXN], mx[MAXN<<2];
void build(int i, int l, int r) {
mx[i] = -INF;
if(l == r) { num[l] = i; return; }
int mid = (l + r) >> 1;
build(i<<1, l, mid);
build(i<<1|1, mid+1, r);
}
void modify(int i, int l, int r, int x, double val) {
chkmax(mx[i], val);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) modify(i<<1, l, mid, x, val);
else modify(i<<1|1, mid+1, r, x, val);
}
double query(int i, int l, int r, int x, int y) {
if(x > y) return -INF;
if(l == x && r == y) return mx[i];
int mid = (l + r) >> 1;
if(y <= mid) return query(i<<1, l, mid, x, y);
else if(x > mid) return query(i<<1|1, mid+1, r, x, y);
else return max(query(i<<1, l, mid, x, mid), query(i<<1|1, mid+1, r, mid+1, y));
}
double tmp[MAXN];
bool solve(int u, int ff) {
modify(1, 1, n, dfn[u], dis[u]);
if(son[u]) {
dis[son[u]] = dis[u] + e[Eson[u]].w;
if(solve(son[u], u)) return 1;
}
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff && v != son[u]) {
dis[v] = dis[u] + e[i].w;
if(solve(v, u)) return 1;
for(int j = 1; j <= mxd[v]-dep[u]; ++j) {
tmp[j] = mx[num[dfn[v]+j-1]];
if(j <= R) {
double temp = query(1, 1, n, dfn[u] + max(L-j, 0), dfn[u] + min(R-j, mxd[u]-dep[u]));
if(tmp[j] + temp - 2 * dis[u] >= 0) return 1;
}
}
for(int j = 1; j <= mxd[v]-dep[u]; ++j)
modify(1, 1, n, dfn[u]+j, tmp[j]);
}
return query(1, 1, n, dfn[u]+L, dfn[u]+min(R, mxd[u]-dep[u]))-dis[u] >= 0;
}
inline bool judge(double mid) {
for(int i = 0; i < cnt; ++i)
e[i].w = init_len[i] - mid;
build(1, 1, n);
return solve(1, 0);
}
int main() {
memset(fir, -1, sizeof fir);
read(n), read(L), read(R);
for(int i = 1, x, y, z; i < n; ++i)
read(x), read(y), read(z), add(x, y, z);
dfs1(1, 0), dfs2(1, 0);
double l = 0, r = 1e6, mid;
while(r - l > (1e-4)) {
mid = (l + r) / 2;
if(judge(mid)) l = mid;
else r = mid;
}
printf("%.3f
", l);
}
CODE2
把二分转成迭代后直接洛谷rank 1了…
迭代就是随便取一个值作为mid,带进去算后得到更优的答案,然后把更优的答案作为mid继续迭代下去…直白点就是向答案逼近.
然后初值取一个适中的数就跑的超快了…感觉相当于没有了二分的那一个log
那分数规划都可以用迭代咯…
#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
template<class T>inline void chkmax(T &x, T y) { if(x < y) x = y; }
const int MAXN = 100005;
const double INF = 1e16;
int n, L, R, cnt, fir[MAXN], init_len[MAXN<<1];
struct edge { int to, nxt; double w; }e[MAXN<<1];
inline void add(int u, int v, int wt) {
e[cnt] = (edge) { v, fir[u], 0 }, init_len[cnt] = wt, fir[u] = cnt++;
e[cnt] = (edge) { u, fir[v], 0 }, init_len[cnt] = wt, fir[v] = cnt++;
}
int mxd[MAXN], dep[MAXN], son[MAXN], Eson[MAXN], dfn[MAXN], tmr;
void dfs1(int u, int ff) {
mxd[u] = dep[u] = dep[ff] + 1;
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff) {
dfs1(v, u); chkmax(mxd[u], mxd[v]);
if(mxd[v] > mxd[son[u]]) son[u] = v, Eson[u] = i;
}
}
void dfs2(int u, int ff) {
dfn[u] = ++tmr;
if(son[u]) dfs2(son[u], u);
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff && v != son[u])
dfs2(v, u);
}
int num[MAXN];
double dis[MAXN];
struct node {
double x; int y; //x:最大路径和 y:边数
node(){}
node(double xx, int yy):x(xx), y(yy){}
inline bool operator <(const node &o)const { return x < o.x; }
}Ans, tmp[MAXN], mx[MAXN<<2];
void build(int i, int l, int r) {
mx[i] = node(-INF, 0);
if(l == r) { num[l] = i; return; }
int mid = (l + r) >> 1;
build(i<<1, l, mid);
build(i<<1|1, mid+1, r);
}
void modify(int i, int l, int r, int x, node val) {
chkmax(mx[i], val);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) modify(i<<1, l, mid, x, val);
else modify(i<<1|1, mid+1, r, x, val);
}
node query(int i, int l, int r, int x, int y) {
if(x > y) return node(-INF, 0);
if(l == x && r == y) return mx[i];
int mid = (l + r) >> 1;
if(y <= mid) return query(i<<1, l, mid, x, y);
else if(x > mid) return query(i<<1|1, mid+1, r, x, y);
else return max(query(i<<1, l, mid, x, mid), query(i<<1|1, mid+1, r, mid+1, y));
}
void solve(int u, int ff) {
modify(1, 1, n, dfn[u], node(dis[u], dep[u]));
if(son[u]) dis[son[u]] = dis[u] + e[Eson[u]].w, solve(son[u], u);
for(int i = fir[u], v; ~i; i = e[i].nxt)
if((v=e[i].to) != ff && v != son[u]) {
dis[v] = dis[u] + e[i].w, solve(v, u);
for(int j = 1; j <= mxd[v]-dep[u]; ++j) {
tmp[j] = mx[num[dfn[v]+j-1]];
if(j <= R) {
node temp = query(1, 1, n, dfn[u] + max(L-j, 0), dfn[u] + min(R-j, mxd[u]-dep[u]));
chkmax(Ans, node(tmp[j].x + temp.x - 2 * dis[u], tmp[j].y + temp.y - 2*dep[u]));
}
}
for(int j = 1; j <= mxd[v]-dep[u]; ++j)
modify(1, 1, n, dfn[u]+j, tmp[j]);
}
node temp = query(1, 1, n, dfn[u]+L, dfn[u]+min(R, mxd[u]-dep[u]));
temp.x -= dis[u]; temp.y -= dep[u];
chkmax(Ans, temp);
}
inline node judge(double mid) {
for(int i = 0; i < cnt; ++i)
e[i].w = init_len[i] - mid;
build(1, 1, n);
Ans = node(-INF, 0);
solve(1, 0);
return Ans;
}
int main() {
memset(fir, -1, sizeof fir);
read(n), read(L), read(R);
for(int i = 1, x, y, z; i < n; ++i)
read(x), read(y), read(z), add(x, y, z);
dep[0] = -1; dfs1(1, 0), dfs2(1, 0);
double mid = 600000;
while(1) { //高级操作
node now = judge(mid);
double ans = (now.x + mid*now.y) / now.y; //把y条边减去的mid加回来,再算一次平均值
if(fabs(ans-mid) < 1e-3) break;
mid = ans;
}
printf("%.3f
", mid);
}