[长链剖分][线段树] Bzoj P1758 重建计划

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

题解

• 我们需要处理出每棵子树中每个深度的dis的最大值，就可以用长链剖分+线段树来维护

• 先递归长儿子，然后继承长儿子的信息，最后合并短儿子的同时顺便维护答案

• 我们可以先预处理出长链剖分序，也就是在求dfs序的时候先递归长儿子

• 这样的话必然满足长儿子的子树的大小必然大于该点为根的树的最大深度，这样我们就可以把深度信息用一棵线段树来储存，那么递归完长儿子后该点就可以直接继承长儿子的答案

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=100010;
const double eps=1e-4,inf=1e15;
int n,L,R,cnt,head[N],deep[N],mx[N],son[N],dfn[N],num[N];
double ans,tmp[N],dis[N];
struct tree{int l,r;double mx;}t[N*5];
struct edge{int to,from,w;double v;}e[N*2];
void insert(int x,int y,int v)
{
    e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].w=v;
    e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].w=v;
}
void dfs1(int x,int fa)
{
    deep[x]=deep[fa]+1,mx[x]=deep[x];
    for (int i=head[x];i;i=e[i].from)
        if (e[i].to!=fa) 
        {
            dfs1(e[i].to,x),mx[x]=max(mx[x],mx[e[i].to]);
            if (mx[e[i].to]>mx[son[x]]) son[x]=e[i].to;
        }
}
void dfs2(int x,int fa)
{
    dfn[x]=++dfn[0];
    if (son[x]) dfs2(son[x],x);
    for (int i=head[x];i;i=e[i].from) if (e[i].to!=fa&&e[i].to!=son[x]) dfs2(e[i].to,x);
}
void build(int d,int l,int r)
{
    t[d].mx=-inf;
    if (l==r) { num[l]=d; return; }
    int mid=l+r>>1;
    build(d*2,l,mid),build(d*2+1,mid+1,r);
}
void modify(int d,int l,int r,int x,double y)
{
    if (l==r) { t[d].mx=max(t[d].mx,y); return; }
    int mid=l+r>>1;
    if (x<=mid) modify(d*2,l,mid,x,y); else modify(d*2+1,mid+1,r,x,y);
    t[d].mx=max(t[d*2].mx,t[d*2+1].mx);
}
double query(int d,int l,int r,int x,int y)
{
    if (x>y) return -inf;
    if (l==x&&r==y) return t[d].mx;
    int mid=l+r>>1;
    return max(query(d*2,l,mid,x,min(y,mid)),query(d*2+1,mid+1,r,max(x,mid+1),y));
}
void dfs(int x,int fa)
{
    modify(1,1,n,dfn[x],dis[x]);
    for (int i=head[x];i;i=e[i].from) if (e[i].to==son[x]) dis[e[i].to]=dis[x]+e[i].v,dfs(e[i].to,x);
    for (int i=head[x];i;i=e[i].from)
        if (e[i].to!=fa&&e[i].to!=son[x])
        {
            dis[e[i].to]=dis[x]+e[i].v,dfs(e[i].to,x);
            for (int j=1;j<=mx[e[i].to]-deep[x];j++)
            {
                tmp[j]=t[num[dfn[e[i].to]+j-1]].mx;
                if (j<=R) ans=max(ans,query(1,1,n,max(1,dfn[x]+L-j),min(dfn[x]+mx[x]-deep[x],dfn[x]+R-j))+tmp[j]-2*dis[x]);
            }
            for (int j=1;j<=mx[e[i].to]-deep[x];j++) modify(1,1,n,dfn[x]+j,tmp[j]);
        }
    ans=max(ans,query(1,1,n,dfn[x]+L,min(dfn[x]+mx[x]-deep[x],dfn[x]+R))-dis[x]);
}
int main()
{
    scanf("%d%d%d",&n,&L,&R);
    for (int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),insert(x,y,z);
    dfs1(1,0),dfs2(1,0);
    double l=0,r=1000000; t[0].mx=-inf;
    while (r-l>eps)
    {
        double mid=(l+r)/2;
        for (int i=1;i<=cnt;i++) e[i].v=e[i].w-mid;
        ans=-inf,dis[1]=0,build(1,1,n),dfs(1,0);
        if (ans<=0) r=mid; else l=mid;
    }
    printf("%.3lf",l);
}