P4292 [WC2010]重建计划

题目描述

\(X\)国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉睫。\(X\)国由\(N\)个城市组成, 重建小组提出，仅需建立\(N-1\)条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含\(N-1\)条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路\(e\)建设之后可以带来的价值\(v(e)\)。

由于重建计划复杂而艰难，经费也有一定限制。因此，*要求第一期重建工程修建的道路数目为\(k\)条，但需满足\(L ≤ k ≤ U\), 即不应少于\(L\)条，但不超过\(U\)条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的\(k\)条路径可以构成一个排列\(e_1 = (p_1, q_1), e_2 = (p_2, q_2),\dots, e_k = (p_k, q_k)\), 对于 \(1 ≤ i < k\), 有\((q_i = p_i+1)\)。

重建小组打算修改他们的原有方案以满足要求，即在原有的N-1条道路中寻找一条路径S作为新的方案，使得新方案中的道路平均价值

最大。这里\(v(e)\)表示道路\(e\)的价值，\(|S|\)表示新方案中道路的条数。请你帮助重建小组寻找一个最优方案。 注: 在本题中\(L\)和\(U\)的设置将保证有解。

输入输出格式

输入格式：

第一行包含一个正整数\(N\)，表示\(X\)国的城市个数。

第二行包含两个正整数\(L\)、\(U\)，表示*要求的第一期重建方案中修建道路数的上下限。

接下来的\(N-1\)行描述重建小组的原有方案，每行三个正整数\(a_i, b_i, v_i\)，分别表示道路\((a_i, b_i)\)，其价值为\(v_i\)。其中城市由\(1\dots N\)标号。

输出格式：

仅包含一行，为一个实数\(AvgValue\)，即最大平均价值。

小数点后保留三位。

说明

对于\(20\%\)的数据，\(N ≤ 5 000\);

另有\(30\%\)的数据，\(N ≤ 100 000\), 原有方案恰好为一条路径(链);

对于\(100\%\)的数据，\(N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, v_i ≤ 10^6\)。

鉴于本辣鸡代码写的天昏地暗，把自己恶心的不行，所以思路也懒得好好说了，简单说一下吧。

分数规划+线段树维护长链剖分

二分之后需要找一条长度为\([l,r]\)之间的链的边权和大于\(0\)

显然可以\(O(n^2)\)进行\(dp\)，然后使用长链剖分继承重儿子。

发现继承重儿子的过程需要开一个线段树维护。

只开一个线段树维护\(dfs\)序，然后就可以很方便的进行偏移，加连接重儿子的边时可以直接区间打\(tag\)

Code:

// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

const int N=1e5+10;

int head[N],to[N<<1],Next[N<<1],cnt;

double edge[N<<1];

void add(int u,int v,double w)

{

    to[++cnt]=v,Next[cnt]=head[u],edge[cnt]=w,head[u]=cnt;

}

double tag[N<<2],mx[N<<2];

int n,lp,rp;

using std::min;

using std::max;

#define ls id<<1

#define rs id<<1|1

void pushdown(int id)

{

    if(tag[id]<-1e17) return;

    if(mx[ls]<-1e17) mx[ls]=tag[id];

    else mx[ls]+=tag[id];

    if(mx[rs]<-1e17) mx[rs]=tag[id];

    else mx[rs]+=tag[id];

    if(tag[ls]<-1e17) tag[ls]=tag[id];

    else tag[ls]+=tag[id];

    if(tag[rs]<-1e17) tag[rs]=tag[id];

    else tag[rs]+=tag[id];

    tag[id]=-1e18;

}

double query(int id,int L,int R,int l,int r)

{

    if(L==l&&R==r) return mx[id];

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));

}

void change(int id,int L,int R,int l,int r,double d)

{

    if(L==l&&R==r)

    {

        if(mx[id]<-1e17) mx[id]=d;

        else mx[id]+=d;

        if(tag[id]<-1e17) tag[id]=d;

        else tag[id]+=d;

        return;

    }

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) change(ls,L,Mid,l,r,d);

    else if(l>Mid) change(rs,Mid+1,R,l,r,d);

    else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);

    mx[id]=max(mx[ls],mx[rs]);

}

void modify(int id,int l,int r,int p,double d)

{

    if(l==r) {mx[id]=max(mx[id],d);return;}

    pushdown(id);

    int mid=l+r>>1;

    if(p<=mid) modify(ls,l,mid,p,d);

    else modify(rs,mid+1,r,p,d);

    mx[id]=max(mx[ls],mx[rs]);

}

int dis[N],ws[N],dfn[N],dfsclock;

double ans;

void dfsinit(int now,int fa)

{

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=fa)

        {

            dfsinit(v,now);

            if(dis[to[ws[now]]]<dis[v]) ws[now]=i;

        }

    dis[now]=dis[to[ws[now]]]+1;

}

int tn,ty;

void dfsseg(int id,int L,int R,int l,int r,int p)

{

    if(L==R)

    {

        int len=l+1-tn;

        if(ty) modify(1,1,n,len+dfn[p],mx[id]);

        else if(len+dis[p]-1>=lp&&len<rp)

            ans=max(ans,mx[id]+query(1,1,n,max(dfn[p]+1,dfn[p]+lp-len),min(dfn[p]+rp-len,dfn[p]+dis[p]-1)));

        return;

    }

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) dfsseg(ls,L,Mid,l,r,p);

    else if(l>Mid) dfsseg(rs,Mid+1,R,l,r,p);

    else dfsseg(ls,L,Mid,l,Mid,p),dfsseg(rs,Mid+1,R,Mid+1,r,p);

}

void dfs(int now,int fa)

{

    dfn[now]=++dfsclock;

    if(ws[now])

    {

        dfs(to[ws[now]],now);

        change(1,1,n,dfn[now]+1,dfn[now]+1,edge[ws[now]]);

        if(dis[now]>2)

            change(1,1,n,dfn[now]+2,dfn[now]+dis[now]-1,edge[ws[now]]);

    }

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=fa&&i!=ws[now])

        {

            dfs(v,now);tn=dfn[v];

            change(1,1,n,dfn[v],dfn[v]+dis[v]-1,edge[i]);

            ty=0,dfsseg(1,1,n,dfn[v],dfn[v]+dis[v]-1,now);

            ty=1,dfsseg(1,1,n,dfn[v],dfn[v]+dis[v]-1,now);

        }

    if(dis[now]-1>=lp)

        ans=max(ans,query(1,1,n,dfn[now]+lp,min(dfn[now]+rp,dfn[now]+dis[now]-1)));

}

bool check(double d)

{

    for(int i=1;i<=cnt;i++) edge[i]-=d;

    for(int i=1;i<=n<<2;i++) mx[i]=tag[i]=-1e18;

    dfsclock=0,ans=-1e18;dfs(1,0);

    for(int i=1;i<=cnt;i++) edge[i]+=d;

    return ans>=0;

}

int main()

{

    scanf("%d%d%d",&n,&lp,&rp);

    double l=1e18,r=-1e18,w;

    for(int u,v,i=1;i<n;i++)

    {

        scanf("%d%d%lf",&u,&v,&w),add(u,v,w),add(v,u,w);

        l=min(l,w),r=max(r,w);

    }

    dfsinit(1,0);

    while(l+1e-4<r)

    {

        double mid=(l+r)/2;

        if(check(mid)) l=mid;

        else r=mid;

    }

    printf("%.3lf\n",l);

    return 0;

}

2018.12.14