自主网站制作,wordpress关闭缓存,河北软件开发网站建设,wordpress开启评论验证码正题
题目链接:https://www.luogu.com.cn/problem/P4292 题目大意
给出nnn个点的一棵树#xff0c;然后求长度在[L,U][L,U][L,U]之间的一条路径的平均权值最大。 解题思路
先上二分0/10/10/1分数规划#xff0c;然后变成求最长在[L,U][L,U][L,U]之间的路径。
很经典的点分…正题
题目链接:https://www.luogu.com.cn/problem/P4292 题目大意
给出nnn个点的一棵树然后求长度在[L,U][L,U][L,U]之间的一条路径的平均权值最大。 解题思路
先上二分0/10/10/1分数规划然后变成求最长在[L,U][L,U][L,U]之间的路径。
很经典的点分治问题但是用线段树会TTT当然可以用单调队列但是我不会。
可以试下上长剖线段树维护链上每个深度的最大值权值。然后枚举短的那条链的时候在长的那条上面线段树查询就好了。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
const double inf1e18,eps1e-6;
struct node{int to,next;double w;
}a[N1];
int n,L,U,tot,cnt,ls[N];
int dep[N],len[N],son[N],rt[N];
double f[N],nw[N],ans;
struct SegTree{double w[N5];int ls[N5],rs[N5];void Change(int x,int L,int R,int pos,double val){if(!x)xcnt,ls[x]rs[x]0,w[x]-inf;if(LR){w[x]max(val,w[x]);return;}int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid1,R,pos,val);w[x]max(w[ls[x]],w[rs[x]]);return;}double Ask(int x,int L,int R,int l,int r){if(lL)lL;if(rR)rR;if(!x||lr)return -inf;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);return max(Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid1,R,mid1,r));}
}T;
void addl(int x,int y,double w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(int x,int fa){dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);if(len[y]len[son[x]])son[x]y,nw[x]a[i].w;}len[x]len[son[x]]1;return;
}
void solve(int x,int fa,int t,double k,double dis){rt[x]0;if(son[x])solve(son[x],x,t,k,disnw[x]-k);T.Change(rt[t],dep[t],dep[t]len[t],dep[x],dis);for(int ils[x];i;ia[i].next){int ya[i].to;if(yson[x]||yfa)continue;solve(y,x,y,k,disa[i].w-k);for(int jdep[y];jdep[y]len[y];j){f[j]T.Ask(rt[y],dep[y],dep[y]len[y],j,j);ansmax(ans,f[j]T.Ask(rt[t],dep[t],dep[t]len[t],2*dep[x]L-j,2*dep[x]U-j)-2*dis);}for(int jdep[y];jdep[y]len[y];j)T.Change(rt[t],dep[t],dep[t]len[t],j,f[j]);}ansmax(ans,T.Ask(rt[t],dep[t],dep[t]len[t],dep[x]L,dep[x]U)-dis);return;
}
bool check(double k){ansT.w[0]-inf;cnt0;solve(1,1,1,k,0);return ans-eps;
}
int main()
{ scanf(%d%d%d,n,L,U);for(int i1;in;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}len[0]-1;dfs(1,1);double l0,r1e6;while(r-leps){double mid(lr)/2.0;if(check(mid))lmid;else rmid;}check(1e6);printf(%.3lf,(lr)/2.0);return 0;
}
