题解 P4292 【[WC2010]重建计划】

这题其实有坑…… 有一个做法可以hack掉网上大部分的题解 并且luogu上有这样的数据，所以不要认为你T了是常数大 ______________________ 题意简单明了，求树上长度在L到R内的路径，使得路径的平均值最大 那么也就是最大化这个式子 ## $\frac{\sum_{}val_{u,v}}{\sum len_{u,v}}$ 然后这里是01分数规划问题，有一个非常经典的套路叫二分答案 我们假设答案是mid，然后判断最优解比mid大还是比mid小 换言之我们要验证不等式 ## $\frac{\sum val_{u,v}}{\sum len_{u,v}}\leq mid$ 是否成立 所以说我们可以将这个不等式变一下形…… ## $\sum val_{u,v}-len_{u,v}mid \leq 0$ 所以说这就非常方便我们验证了，我们只需要将每一个边都减去mid然后判定一下有没有负的路径即可 找负路径的话我们可以将这个问题转化为长度在[L,R]中寻找最小的路径 一看有长度限制……当然是点分治啦…… 所以我们还是老套路，对这颗树进行点分治，此时我们考虑过分治重心g的所有路径 暴力的从分治重心dfs一遍然后求出每一个路径的距离和深度 现在我们要做的是“拼合”两条路径 那么，怎么拼合呢？ 当然是对于每一个路径求出和它匹配的最优的一个路径了…… 但是我们还有深度的限制，换句话说我们能和这个路径匹配的路径的深度必须在一个区间里 如果对深度建权值线段树的话我们会发现情况十分辣手，因为复杂度此时猛增至 $O(nlog^3n)$根本过不去 此时你可能会说，如果把割掉g之后每一个子联通块中的路径按照深度排序，那么随着深度的递增，可以和当前路径匹配的路径的深度区间左右端点是单调递增的 此时我们就可以愉快的使用单调队列，复杂度成功优化至$O(nlog^2n)$皆大欢喜？ 此时你会发现你复杂度分析存在一个漏洞，每次初始化的复杂度是$min(R-L,max(dep))$的其中$max(dep)$为这个联通块之前的联通块的最深深度 所以我们可以构造一个长度为2/3n的长链，在中点处构造一个3/n的菊花，此时我们就可以愉快的把你卡成$O(n^2logn)$ 为了避免这个情况需要把联通块们按照最大深度进行排序，然后按照这个顺序插入路径，关于同一个深度的路径，我们使用以深度为下标的数组存储路径的带权长度 此时我们就可以愉快的使用单调队列进行求解最小值的操作了 然后就是大力二分套在外面啦~ 对了，为了优化常数，请将点分树提前建好，不然可能因为常数巨大而T飞 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<vector> using namespace std;const int N=1e5+10;typedef double db;const db eps=1e-9; int v[2*N];int x[2*N];int al[N];int ct;db val[2*N];int siz[N];bool book[N]; bool cut[N];db mxv[N];int q[N];int hd;int tl;int L;int R;int n; struct data{int dep;db v;friend bool operator <(data a,data b){return a.dep>b.dep;}}; struct chi//对每个联通块排序 { int mxdep;vector <data> ve; inline void push(const data& da){mxdep=max(mxdep,da.dep);ve.push_back(da);} inline void srt(){sort(ve.begin(),ve.end());} };vector <chi> s[N]; inline bool cmp(const chi& a,const chi& b){return a.mxdep<b.mxdep;} inline void add(int u,int V,db va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} inline int dfs1(int u)//siz { book[u]=true;siz[u]=1; for(int i=al[u];i;i=x[i])if(!book[v[i]]&&!cut[v[i]])siz[u]+=dfs1(v[i]); book[u]=false;return siz[u]; } inline int find(int u,const int& tot)//重心 { book[u]=true;int ret=u; for(int i=al[u];i;i=x[i]) if(!book[v[i]]&&!cut[v[i]]&&2*siz[v[i]]>=tot){ret=find(v[i],tot);break;} book[u]=false;return ret; } inline void dfs2(int u,vector <chi>::iterator ve,int dep,db dis) { book[u]=true;ve->push((data){dep,dis}); for(int i=al[u];i;i=x[i])if(!book[v[i]]&&!cut[v[i]])dfs2(v[i],ve,dep+1,dis+val[i]); book[u]=false; } inline void solve(int u)//构建点分树 { dfs1(u);int g=find(u,siz[u]);cut[g]=true; for(int i=al[g];i;i=x[i]) { if(cut[v[i]])continue;s[g].push_back(chi()); dfs2(v[i],--s[g].end(),1,val[i]);(--s[g].end())->srt(); }sort(s[g].begin(),s[g].end(),cmp); for(int i=al[g];i;i=x[i]){if(!cut[v[i]])solve(v[i]);} } inline bool jud(db ans)//每次在点分树上拼合路径 { vector <chi>::iterator it1;vector <data>::iterator it2; for(int i=1;i<=n;i++)mxv[i]=-0x7f7f7f7f;bool ret=false; for(int i=1,nwdep;i<=n;i++) { for(it1=s[i].begin(),nwdep=0;it1!=s[i].end();nwdep=it1->mxdep,++it1) { int dr=0; for(it2=it1->ve.begin(),hd=1,tl=0;it2!=it1->ve.end();++it2)//单调队列 { int nl=max(0,(int)(L-it2->dep));int nr=min(nwdep,(int)(R-it2->dep));if(nl>nr){continue;} for(int np=dr+1;np<=nr;np++){while(hd<=tl&&mxv[q[tl]]<mxv[np])--tl;q[++tl]=np;} while(hd<=tl&&q[hd]<nl){++hd;}dr=nr; if(mxv[q[hd]]+it2->v-ans*it2->dep>eps){ret=true;goto skip;} } for(it2=it1->ve.begin();it2!=it1->ve.end();++it2)//特判到根的路径同时将路径插入到权值数组中 { mxv[it2->dep]=max(mxv[it2->dep],it2->v-ans*it2->dep); if(L<=it2->dep&&it2->dep<=R&&mxv[it2->dep]>eps){ret=true;goto skip;} } }skip:; for(it1=s[i].begin();it1!=s[i].end();++it1) for(it2=it1->ve.begin();it2!=it1->ve.end();++it2) {mxv[it2->dep]=-0x7f7f7f7f;} if(ret)return true; }return false; } int main() { scanf("%d%d%d",&n,&L,&R); for(int i=1,u,v,va;i<n;i++) {scanf("%d%d%d",&u,&v,&va);add(u,v,va);add(v,u,va);} solve(1);db l=0;db r=1e6;//无脑二分 while(r-l>1e-4){db mid=(l+r)/2;(jud(mid)?l:r)=mid;} printf("%.3lf",l);return 0; } ```