bzoj1758 [Wc2010]重建计划

Description

Input

第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号

Output

输出最大平均估值，保留三位小数

Sample Input

4
2 3
1 2 1
1 3 2
1 4 3

Sample Output

2.500

HINT

N<=100000,1<=L<=U<=N-1,Vi<=1000000 新加数据一组 By leoly,但未重测..2016.9.27

正解：分数规划+点分治+单调队列？。

好吧这题我是压常数过去的，并没有用单调队列。。

显然，外层二分答案，然后每条边都减去$mid$，判断是否能找到长度属于$[l,r]$且路径和$>0$的路径。

那么我们点分治，在每一层依次递归重心的所有子树，合并答案就行了，但是属于$[l,r]$这个条件不好处理。正解似乎是单调队列，然而我用的是线段树，复杂度多一个$log$。。

不过还是跑过去了，具体是怎么压常数的呢？

1.加$register$，可以快$2s$。

2.手写$min$,$max$函数，使用三目运算符，可以快将近$1s$。

3.如果当前答案已经$>0$，直接退出分治，但是这个好像对于特意构造的数据作用不大。

4.把每棵子树中深度相同的结点权值直接取$max$，并且记下这些深度，这样可以节省线段树的插入。

5.预处理出所有的重心和在每一层的最大深度，可以快$1s$。

6.用$zkw$线段树，且因为线段树是以深度为区间的，所以我们每一层分治时的线段树就以当前最大深度为上界，这样线段树消耗的$log$可以大大减少。应该说，这个压常是最优秀的，它让线段树的$log$几乎变成了常数，我大概计算了一下，每层改变线段树上界好像使得$log^{2}n$变成了$3log$左右的常数？

大概用这些压常技巧，就能通过这题了。

  1 #include <bits/stdc++.h>
  2 #define N (100010)
  3 #define inf (1e18)
  4 #define eps (3e-4)
  5 #define ls (x<<1)
  6 #define rs (x<<1|1)
  7 #define il inline
  8 #define RG register
  9 #define ll long long
 10 #define min(a,b) (a<b ? a : b)
 11 #define max(a,b) (a>b ? a : b)
 12  
 13 using namespace std;
 14  
 15 struct edge{ int nt,to,dis; }g[N<<1];
 16  
 17 int head[N],st[N],vi[N],vi1[N],vis[N],dep[N],son[N],sz[N],ss[N],RT[N][19],Dp[N][19],n,l,r,num,top,bit,Mx_dep;
 18 double sum[N<<2],dis[N],mx[N],L,R,mid,res,ans;
 19  
 20 il int gi(){
 21   RG int x=0,q=1; RG char ch=getchar();
 22   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 23   if (ch=='-') q=-1,ch=getchar();
 24   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 25   return q*x;
 26 }
 27  
 28 il void insert(RG int from,RG int to,RG int dis){
 29   g[++num]=(edge){head[from],to,dis},head[from]=num; return;
 30 }
 31 
 32 il void build(){ for (RG int i=1;i<=bit+n;++i) sum[i]=-inf; return; }
 33 
 34 il void update0(RG int x,RG double y){
 35   for (x+=bit,sum[x]=max(sum[x],y),x>>=1;x;x>>=1) sum[x]=max(sum[ls],sum[rs]); return;
 36 }
 37 
 38 il void update1(RG int x){
 39   for (sum[x+=bit]=-inf,x>>=1;x;x>>=1) sum[x]=-inf; return;
 40 }
 41 
 42 il double query(RG int l,RG int r){
 43   RG double res=-inf;
 44   for (l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
 45     if (~l&1) res=max(res,sum[l^1]);
 46     if (r&1) res=max(res,sum[r^1]);
 47   }
 48   return res;
 49 }
 50 
 51 il void getroot(RG int x,RG int p,RG int S,RG int &rt){
 52   sz[x]=1,son[x]=0; RG int v;
 53   for (RG int i=head[x];i;i=g[i].nt){
 54     v=g[i].to; if (v==p || vis[v]) continue;
 55     getroot(v,x,S,rt),sz[x]+=sz[v];
 56     son[x]=max(son[x],sz[v]);
 57   }
 58   son[x]=max(son[x],S-sz[x]);
 59   if (son[rt]>=son[x]) rt=x; return;
 60 }
 61 
 62 il void getdep(RG int x,RG int p){
 63   dep[x]=dep[p]+1,Mx_dep=max(Mx_dep,dep[x]); RG int v;
 64   for (RG int i=head[x];i;i=g[i].nt){
 65     v=g[i].to; if (v==p || vis[v]) continue;
 66     getdep(v,x);
 67   }
 68   return;
 69 }
 70 
 71 il void getdis(RG int x,RG int p,RG double key){
 72   dep[x]=dep[p]+1,sz[x]=1; RG int v,k=dep[x];
 73   if (!vi[k]) st[++top]=k,vi[k]=1; mx[k]=max(mx[k],dis[x]);
 74   for (RG int i=head[x];i;i=g[i].nt){
 75     v=g[i].to; if (v==p || vis[v]) continue;
 76     dis[v]=dis[x]+g[i].dis-key;
 77     getdis(v,x,key),sz[x]+=sz[v];
 78   }
 79   return;
 80 }
 81 
 82 il void solve0(RG int x,RG int S,RG int level){
 83   RG int rt=0; Mx_dep=0,son[0]=S;
 84   getroot(x,0,S,rt),vis[rt]=1,RT[x][level]=rt;
 85   for (RG int i=head[rt];i;i=g[i].nt)
 86     if (!vis[g[i].to]) getdep(g[i].to,0);
 87   Dp[x][level]=Mx_dep;
 88   for (RG int i=head[rt];i;i=g[i].nt)
 89     if (!vis[g[i].to]) solve0(g[i].to,sz[g[i].to],level+1);
 90   return;
 91 }
 92 
 93 il int solve(RG int x,RG int S,RG int level,RG double key){
 94   RG int rt=RT[x][level],Mx=Dp[x][level],tp=0; vis[rt]=1;
 95   for (bit=1;bit<=Mx+1;bit<<=1);
 96   for (RG int i=head[rt],v;i;i=g[i].nt){
 97     v=g[i].to; if (vis[v]) continue;
 98     top=0,dis[v]=g[i].dis-key,getdis(v,0,key);
 99     for (RG int j=1,L,R,k;j<=top;++j){
100       k=st[j]; if (l<=k && k<=r) res=max(res,mx[k]); if (res>eps) return 1;
101       if (!vi1[k]) ss[++tp]=k,vi1[k]=1; L=max(l-k,1),R=min(r-k,Mx);
102       if (L<=R) res=max(res,mx[k]+query(L,R)); if (res>eps) return 1;
103     }
104     for (RG int j=1,k;j<=top;++j)
105       k=st[j],update0(k,mx[k]),mx[k]=-inf,vi[k]=0;
106   }
107   for (RG int i=1;i<=tp;++i) update1(ss[i]),vi1[ss[i]]=0;
108   for (RG int i=head[rt];i;i=g[i].nt)
109     if (!vis[g[i].to] && solve(g[i].to,sz[g[i].to],level+1,key)) return 1;
110   return res>eps;
111 }
112  
113 int main(){
114   freopen("rebuild.in","r",stdin);
115   freopen("rebuild.out","w",stdout);
116   n=gi(),l=gi(),r=gi(),L=inf;
117   for (RG int i=1,u,v,w;i<n;++i)
118     u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w),L=min(L,w),R=max(R,w);
119   solve0(1,n,0);
120   while (R-L>eps){
121     mid=(L+R)*0.5,res=-inf; for (bit=1;bit<=n+1;bit<<=1); build();
122     for (RG int i=1;i<=n;++i) mx[i]=-inf,vi[i]=vi1[i]=vis[i]=0;
123     solve(1,n,0,mid)?(ans=mid,L=mid):R=mid;
124   }
125   printf("%0.3lf
",ans); return 0;
126 }