【BZOJ1758】重建计划（点分治）

题意：

给定一棵n个点的树，每条边有权值。
求一条链，这条链包含的边数在L和U之间，且平均边权最大。
N﹤=100000

思路：

做法一：RYZ作业

二分答案再点分治，寻找是否有大于0且边数在L和U之间的链

f[i]为当前子树深度为i的链最大总和，g[i]为前几个深度为i的链最大总和

维护一个下标递增，值递增的单调队列

按子树深度排序一定要加，因为清空与当前子树深度最大值有关，不加的话可能会退化成n^2

改了快一天改不出，还加了迭代，最后发现是分治的时候root打成v，相当于什么都没干……

 var head,vet,next,c,d,size,flag,q1:array[..]of longint;

     p:array[..]of longint;

     len,h,q2:array[..]of double;

     f,g:array[..]of double;

     n,i,tot,root,l1,r1,sum,mx,mxdep,x,y,z,tmp,t,w,now,m:longint;

     eps,oo,mid:double;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 procedure add(a,b,c:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  len[tot]:=c;

  head[a]:=tot;

 end;

 procedure getroot(u,fa:longint);

 var e,v:longint;

 begin

  size[u]:=; p[u]:=;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if (v<>fa)and(flag[v]=) then

   begin

    getroot(v,u);

    size[u]:=size[u]+size[v];

    p[u]:=max(p[u],size[v]);

   end;

   e:=next[e];

  end;

  p[u]:=max(p[u],sum-p[u]);

  if p[u]<p[root] then root:=u;

 end;

 procedure dfs(u,fa,dep:longint;t:double);

 var e,v:longint;

 begin

  if f[dep]<t then f[dep]:=t;

  mx:=max(mx,dep);

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if (v<>fa)and(flag[v]=) then dfs(v,u,dep+,t+len[e]-mid);

   e:=next[e];

  end;

 end;

 procedure ins(k:longint;x:double);

 begin

  while (w>=t)and(q2[w]<x) do dec(w);

  inc(w); q1[w]:=k; q2[w]:=x;

 end;

 procedure del(k:longint);

 begin

  while (t<=w)and(q1[t]>=k) do inc(t);

 end;

 procedure getdep(u,fa,dep:longint);

 var e,v:longint;

 begin

  e:=head[u];

  if dep>d[m] then d[m]:=dep;

  while e<> do

  begin

   v:=vet[e];

   if (v<>fa)and(flag[v]=) then getdep(v,u,dep+);

   e:=next[e];

  end;

 end;

 procedure qsort(l,r:longint);

 var i,j,mid:longint;

     t:double;

 begin

  i:=l; j:=r; mid:=d[(l+r)>>];

  repeat

   while mid>d[i] do inc(i);

   while mid<d[j] do dec(j);

   if i<=j then

   begin

    swap(d[i],d[j]);

    swap(c[i],c[j]);

    t:=h[i]; h[i]:=h[j]; h[j]:=t;

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 function solve(u:longint;avg:double):double;

 var t1,t2,ans,tmp:double;

     v,e,i,j:longint;

 begin

  t1:=avg; t2:=-oo;

  m:=;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if flag[v]= then

   begin

    inc(m);

    getdep(v,u,);

    c[m]:=v; h[m]:=len[e];

   end;

   e:=next[e];

  end;

  if m> then qsort(,m);

  while t1-t2>eps do

  begin

   t2:=t1; mid:=t1; ans:=-oo;

   mxdep:=; g[]:=;

   for j:= to m do

   begin

    v:=c[j];

    mx:=;

    dfs(v,u,,h[j]-mid);

    t:=; w:=;

    for i:=min(mxdep,r1) to l1 do ins(i,g[i]);

    for i:=max(,l1-mxdep) to mx do

    begin

     if l1-i>= then ins(l1-i,g[l1-i]);

     del(r1-i+);

     if t<=w then

      if (f[i]+q2[t])/(q1[t]+i)>ans then

       ans:=(f[i]+q2[t])/(q1[t]+i);

    end;

    mxdep:=max(mxdep,mx);

    for i:= to mx do

     if f[i]>g[i] then g[i]:=f[i];

    for i:= to mx do f[i]:=-oo;

   end;

   for i:= to mxdep do g[i]:=-oo;

   t1:=t1+ans;

  end;

  flag[u]:=; t2:=t1;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if flag[v]= then

   begin

    root:=; sum:=size[v];

    getroot(v,);

    tmp:=solve(root,t1);

    if tmp>t2 then t2:=tmp;

   end;

   e:=next[e];

  end;

  exit(t2);

 end;

 begin

  assign(input,'bzoj1758.in'); reset(input);

  assign(output,'bzoj1758.out'); rewrite(output);

  readln(n);

  readln(l1,r1);

  oo:=1e8;

  for i:= to n- do

  begin

   readln(x,y,z);

   add(x,y,z);

   add(y,x,z);

  end;

  p[]:=n+; root:=; sum:=n;

  eps:=1e-4;

  getroot(,);

  for i:= to n do

  begin

   f[i]:=-oo; g[i]:=-oo;

  end;

  writeln(solve(root,)::);

  close(input);

  close(output);

 end.

做法2：From https://blog.bill.moe/WC2010-rebuild/

建立一个答案表，顺序是长链剖分的dfs序

长链可以共用答案表，轻儿子暴力合并到父亲所在长链中

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,int>P;

 #define N  200010

 #define M  200010

 #define fi first

 #define se second

 #define MP make_pair

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 const ll MOD=1e9+,inv2=(MOD+)/;

       double eps=1e-;

       int INF=<<;

       ll inf=5e13;

       int dx[]={-,,,};

       int dy[]={,,-,};

 double t[N<<];

 int head[N],vet[N],len[N],nxt[N],

     dep[N],son[N],slen[N],fa[N],id[N],dfn[N],mx[N],top[N],

     tot,L,R,tim,n;

 double ans,tmp[N];

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void add(int a,int b,int c)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     len[tot]=c;

     head[a]=tot;

 }

 void build(int l,int r,int p)

 {

     t[p]=-1e18;

     if(l==r)

     {

         id[l]=p;

         return;

     }

     int mid=(l+r)>>;

     build(l,mid,ls);

     build(mid+,r,rs);

 }

 void update(int u,double v)

 {

     int now=id[u];

     while(now)

     {

         t[now]=max(t[now],v);

         now>>=;

     }

 }

 double query(int l,int r,int x,int y,int p)

 {

     if(x<=l&&r<=y) return t[p];

     int mid=(l+r)>>;

     double res=-1e18;

     if(x<=mid) res=max(res,query(l,mid,x,y,ls));

     if(y>mid) res=max(res,query(mid+,r,x,y,rs));

     return res;

 }

 void dfs1(int u,int pre,int d)

 {

     dep[u]=mx[u]=d;

     fa[u]=pre;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(v!=pre)

         {

             dfs1(v,u,d+);

             if(mx[v]>mx[son[u]])

             {

                 son[u]=v;

                 slen[u]=len[e];

                 mx[u]=mx[v];

             }

         }

         e=nxt[e];

     }

 }

 void dfs2(int u,int ance)

 {

     top[u]=ance;

     dfn[u]=++tim;

     if(son[u]) dfs2(son[u],ance);

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

         e=nxt[e];

     }

 }

 double ask(int u,int l,int r)

 {

     l=max(l,);

     r=min(r,mx[u]-dep[u]);

     if(l>r) return -1e18;

     return query(,n,dfn[u]+l,dfn[u]+r,);

 }

 void solve(int u,double d,double mid)

 {

     update(dfn[u],d);

     if(son[u]) solve(son[u],d+slen[u]-mid,mid);

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(v!=fa[u]&&v!=son[u])

         {

             solve(v,d+len[e]-mid,mid);

             rep(j,,mx[v]-dep[v]+)

             {

                 tmp[j]=t[id[dfn[v]+j-]];

                 ans=max(ans,tmp[j]+ask(u,L-j,R-j)-*d);

             }

             rep(j,,mx[v]-dep[v]+) update(dfn[u]+j,tmp[j]);

         }

         e=nxt[e];

     }

     ans=max(ans,ask(u,L,R)-d);

 }

 int isok(double K)

 {

     build(,n,);

     ans=-1e18;

     solve(,,K);

     return ans>=-eps;

 }

 int main()

 {

     n=read(),L=read(),R=read();

     tot=;

     rep(i,,n-)

     {

         int x=read(),y=read(),z=read();

         add(x,y,z);

         add(y,x,z);

     }

     dfs1(,,);

     tim=;

     dfs2(,);

     double left=,right=1e10;

     while(right-left>eps)

     {

         double mid=(left+right)/;

         if(isok(mid)) left=mid;

          else right=mid;

     }

     printf("%.3f\n",left);

     return ;

 }

巴特西

【BZOJ1758】重建计划（点分治）

最新文章

热门文章