解析

第一眼：Wow這么水的黑？？
然后寫了一發二分套線段樹的3log代碼上去
T到飛起，只有40…

無奈瞅了一眼標簽：單調隊列
對啊
于是又寫了一個上去
20
…

好啊
然后就擺爛了
qwq
果然黑題沒有一個好東西

一個關鍵的思想是把新加入的點當做單調隊列中的元素
這樣就能保證在聯通塊較小的時候被卡成R-L導致T飛
其實不難想，思維還是需要加強

此外，本題需要提前把點分治的樹建出來
大大減小常數
而代碼難度幾乎沒有提高

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long //#define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1e5+100; const int M=2e5+10500; const double eps=1e-5; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,L,R,oo; struct node{int to,nxt;double w; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],1.0*w};fi[x]=cnt;return; }bool vis[N]; double dis[N],ans; int dep[N],S,siz[N],mmx[N],rt,G[N];double mx[N]; int q[N],st,ed,tag[N],tim; int nw[N],tot; #define Mx(o) (tag[o]==tim?mx[o]:-2e11)int num; void find(int x,int f){siz[x]=1;mmx[x]=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]||to==f) continue;find(to,x);//printf(" %d->%d siz:%d+=%d\n",x,to,siz[x],siz[to]);siz[x]+=siz[to];mmx[x]=max(mmx[x],siz[to]);}mmx[x]=max(mmx[x],S-siz[x]);if(!rt||mmx[rt]>mmx[x]) rt=x;//printf(" x=%d mx=%d (rt=%d) siz=%d\n",x,mx[x],rt,siz[x]);return; } void init(int x){S=siz[x];rt=0;find(x,0);x=rt;vis[rt]=1;G[++num]=x;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;init(to);} }int jd[N]; void bfs(int x){dep[x]=1;nw[1]=x;jd[x]=tim;int st(1),ed(1);while(st<=ed){int now=nw[st++];for(int i=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]||jd[to]==tim) continue;jd[to]=tim;dep[to]=dep[now]+1;dis[to]=dis[now]+p[i].w;nw[++ed]=to;}}tot=ed; } int debug=0; void solve(int x){//x=G[++num];S=siz[x];rt=0;find(x,0);x=rt;vis[x]=1;++tim;if(debug)printf("\n-----solve:rt=%d\n",x);mx[0]=0;tag[0]=tim;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;dis[to]=p[i].w;bfs(to);st=1,ed=0;int pl(0);if(debug) printf("to=%d\n",to);for(int d=min(R,dep[nw[tot]]);d>=0;d--){int li=L-d,ri=R-d;while(pl<tot&&dep[nw[pl+1]]<=ri){++pl;while(st<=ed&&dis[q[ed]]<=dis[nw[pl]]) ed--;q[++ed]=nw[pl];}while(st<=ed&&dep[q[st]]<li) st++;if(st<=ed) ans=max(ans,dis[q[st]]+Mx(d));if(debug) printf(" d=%d x=%d %.2lf %.2lf\n",d,q[st],dis[q[st]],Mx(d));if(debug) if(ans>=0){printf("!\n");exit(0);}}for(int o=1;o<=tot;o++){int now=nw[o];if(Mx(dep[now])<dis[now]){mx[dep[now]]=dis[now];tag[dep[now]]=tim;}}}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;solve(to);}return; }bool check(double v){for(int i=0;i<=cnt;i++) p[i].w-=v;num=0;memset(vis,0,sizeof(vis));ans=-2e11;siz[1]=n;solve(1);for(int i=0;i<=cnt;i++) p[i].w+=v;//printf("ans=%lf\n",ans);return ans>=0; }int main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();L=read();R=read();//assert(n<=5000);int mn(1000000),mx(0);for(int i=1;i<n;i++){int x=read(),y=read(),w=read();mn=min(mn,w);mx=max(mx,w);addline(x,y,w);addline(y,x,w);}//siz[1]=n;init(1);if(debug){printf("%d\n",check(6.4));return 0;}double st=mn,ed=mx;while(ed-st>eps){double mmid=(st+ed)/2;if(check(mmid)) st=mmid;else ed=mmid;}//printf("%d\n",oo);printf("%.3lf",st);return 0; } /* */

總結

以上是生活随笔為你收集整理的洛谷P4292：重建计划（点分治、单调队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。