dwjshift's Blog

bzoj1758 [WC2010]重建计划

| Comments

好久没写题解了呢。
显然首先要二分答案,把边权都减去,那么就只需要判断有没有边权和大于0且长度符合要求的路径了。
接着就是点分,计算经过重心的最优路径。处理到一棵深度为的子树时,若之前的子树的最大深度为,可以用单调队列在的时间内求出它们之间的最优路径。但是这样复杂度依然是不靠谱的。如果处理的第一棵子树深度很大的话,会导致处理一个重心的复杂度达到。因此,我们得按照深度(或者子树大小)从小到大的顺序来处理子树,这样复杂度就是均摊的了。我做这题的时候翻了很多篇题解,似乎大部分人都没有按照深度从小到大来算,还有的说被卡常数什么的,大概是他们的复杂度本来就不对吧……
我是把二分写在了外面。如果每次分治的时候都重新排序子树的话复杂度会达到3个log,所以要一开始就预处理出来。总的复杂度是
不知为何我的程序跑得挺慢的。似乎有把二分写在点分里面会更快的都市传说,不过我也懒得去优化常数了。

code

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
#define repe(i,x) for (edge *i=fst[x]; i; i=i->nxt)
using namespace std;
 
int n,low,upp,u,v,w,t,flag[100100],root[100100],sz,s[100100],f[100100],clk,
pool[2000000],*tp=pool,*son[100100],tot[100100],dep1,dep2,x,q[100100],head,tail;
double l,r,mid,dis[100100],f1[100100],f2[100100];
struct edge
{
    int v,w;
    edge *nxt;
} poole[200100],*tpe=poole,*fst[100100];
 
void find(int x,int fa)
{
    f[x]=0,s[x]=1;
    repe(i,x)
        if (!flag[i->v] && i->v!=fa)
            find(i->v,x),s[x]+=s[i->v],f[x]=max(f[x],s[i->v]);
    if ((f[x]=max(f[x],sz-s[x]))<f[root[t]])
        root[t]=x;
}
 
inline bool cmp(int x,int y)
{
    return s[x]<s[y];
}
 
void solve(int x)
{
    flag[x]=t,son[x]=tp;
    if (sz==1)
        return;
    repe(i,x)
        if (!flag[i->v])
        {
            if (s[i->v]>s[x])
                s[i->v]=sz-s[x];
            son[x][++tot[x]]=i->v;
        }
    sort(son[x]+1,tp=son[x]+tot[x],cmp);
    repe(i,x)
        if (!flag[i->v])
            ++t,sz=s[i->v],find(i->v,0),solve(root[t]);
}
 
void dfs(int x,int fa,int dep,double w)
{
    if (dep>upp)
        return;
    dep2=max(dep2,dep),f2[dep]=max(f2[dep],w);
    repe(i,x)
        if (flag[i->v]>clk && i->v!=fa)
            dfs(i->v,x,dep+1,w+i->w-mid);
}
 
void insert(int x)
{
    for (; head<=tail && f1[q[tail]]<f1[x]; --tail);
    q[++tail]=x;
}
 
bool check()
{
    for (clk=1; clk<=n; ++clk)
    {
        dep1=0,x=root[clk];
        repe(i,x)
            dis[i->v]=i->w-mid;
        repu(i,1,tot[x])
        {
            dep2=0,dfs(son[x][i],x,1,dis[son[x][i]]);
            head=0,tail=-1;
            repu(j,max(0,low-dep2),min(dep1,upp-dep2-1))
                insert(j);
            repd(j,dep2,1)
            {
                if (upp-j<=dep1)
                    insert(upp-j);
                if (head<=tail && q[head]+j<low)
                    ++head;
                if (head<=tail && f1[q[head]]+f2[j]>0)
                {
                    repu(k,1,dep2)
                        f1[k]=f2[k]=-(1<<30);
                    return 1;
                }
            }
            repu(j,1,dep2)
                f1[j]=max(f1[j],f2[j]),f2[j]=-(1<<30);
            dep1=dep2;
        }
        repu(i,1,dep1)
            f1[i]=-(1<<30);
    }
    return 0;
}
 
int main()
{
    scanf("%d%d%d",&n,&low,&upp);
    repu(i,1,n-1)
    {
        scanf("%d%d%d",&u,&v,&w);
        *tpe=(edge){v,w,fst[u]},fst[u]=tpe++;
        *tpe=(edge){u,w,fst[v]},fst[v]=tpe++;
    }
    ++t,sz=n,f[0]=1<<30,find(1,0),solve(root[1]);
    repu(i,1,n)
        f1[i]=f2[i]=-(1<<30);
    for (l=1,r=1000000; l+1e-4<r;)
    {
        mid=(l+r)/2;
        (check()?l:r)=mid;
    }
    printf("%.3f\n",l);
    return 0;
}

Comments

comments powered by Disqus