BZOJ1758 [Wc2010]重建计划

2014.12.11 19:53 Thu| 12 visits oi_2015| 2015_刷题日常| Text

一道可爱的树的点分治。

Solution

题意即找出一条经过边数在区间 $(L,U)$ 内的一条路径,使得经过的边权的平均值最大。输出这一平均值。直接点分治即可。

对于当前递归到的树,以其重心为根,求出它的每一个子树的深度,并将子树以深度为关键字从小到大排序。依次枚举子树,寻找这棵子树中每一个深度的点到根的距离的最大值。和之前的子树使用单调队列在一起更新答案。之后合并两部分子树即可。

//把.first写成了.second,竟然只有最后一个点WA了,其余的都是T的不是很离谱?什么情况?

好吧,最终用时3220ms,某某小朋友用偏心的二分卡常数过的是什么心态?

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define inf 0x3f3f3f3f

int n,L,U,root;
double ans,maxv;
long long dist[N],pre[N],pos[N];
int size[N],maxs[N],vis[N],deep[N];
int head[N],next[2*N],to[2*N],val[2*N],cnt;

inline void add(int x,int y,int z)
{
    to[++cnt]=y; val[cnt]=z;
    next[cnt]=head[x]; head[x]=cnt;
}

void getroot(int sum,int x,int fa)
{
    size[x]=1; maxs[x]=0;
    for(int i=head[x],y;i;i=next[i])
        if(!vis[y=to[i]]&&y!=fa)
            getroot(sum,y,x),size[x]+=size[y],maxs[x]=max(maxs[x],size[y]);
    maxs[x]=max(maxs[x],sum-size[x]);
    if(maxs[x]<maxs[root]) root=x;
}

int getdeep(int x,int fa,int d1,long long d2)
{
    deep[x]=d1; dist[x]=d2; int re=d1;
    for(int i=head[x],y;i;i=next[i])
        if(!vis[y=to[i]]&&y!=fa)
            re=max(re,getdeep(y,x,d1+1,d2+val[i]));
    return re;
}

void getdist(int x,int fa)
{
    pos[deep[x]]=max(pos[deep[x]],dist[x]);
    for(int i=head[x],y;i;i=next[i])
        if(!vis[y=to[i]]&&y!=fa)
            getdist(y,x);
}

double tpx[N],tpy[N];

bool check(double w,int prel,int posl)
{
    for(int i=1;i<=prel;i++) tpx[i]=(double)pre[i]-i*w;
    for(int i=1;i<=posl;i++) tpy[i]=(double)pos[i]-i*w;
    deque<int> q;
    for(int i=1;i<=min(U-prel,posl);i++)
    {
        while(!q.empty()&&tpy[i]>=tpy[q.back()]) q.pop_back();
        q.push_back(i);
    }
    for(int i=prel;i;i--)
    {
        if(U-i>=1&&U-i<=posl)
        {
            while(!q.empty()&&tpy[U-i]>=tpy[q.back()]) q.pop_back();
            q.push_back(U-i);
        }
        while(!q.empty()&&q.front()+i<L) q.pop_front();
        if(!q.empty()&&tpy[q.front()]+tpx[i]>=0) return true;
    }
    return false;
}

void update(int prel,int posl)
{
    double l=ans,r=maxv,mid;
    while(r-l>1e-4)
    {
        mid=(r+l)/2.0;
        if(check(mid,prel,posl)) l=mid;
        else r=mid;
    }
    ans=max(ans,l);
}

pair<int,int> son[N];

void getans(int x)
{
    int num=0; vis[x]=1;
    for(int i=head[x],y;i;i=next[i])
        if(!vis[y=to[i]])
            son[++num]=make_pair(getdeep(y,x,1,val[i]),y);
    if(!num) return;
    sort(son+1,son+num+1);
    memset(pre,0xc0,(son[num].first+1)*sizeof(long long));
    for(int i=1;i<=num;i++)
    {
        memset(pos,0xc0,(son[i].first+1)*sizeof(long long));
        getdist(son[i].second,x);
        if(i>=2)
            if(son[i].first+son[i-1].first>=L)
                update(son[i-1].first,son[i].first);
        for(int j=1;j<=son[i].first;j++)
            pre[j]=max(pre[j],pos[j]);
    }
    for(int i=head[x],y;i;i=next[i])
        if(!vis[y=to[i]])
            root=0,getroot(size[y],y,x),getans(root);
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>n>>L>>U;
    for(int i=1,x,y,z;i<n;i++)
        x=read(), y=read(), z=read(),
        add(x,y,z), add(y,x,z), maxv=max(maxv,(double)z);
    maxs[0]=inf;
    getroot(n,1,0);
    getans(root);
    printf("%.3lf\n",ans);
}