WC2010 重建计划

This post is written in Chinese. Please consider using Google Translate

问题简述

给定一棵边上带权的树,求一个平均价值最大的简单路径。路径的平均价值定义为路径的带权长度与不带权长度的比值。

问题分析

在一棵树上直接找这样的路径是很困难的,因此我们考虑将问题分解。一个基本的想法是在树上分治,为保证对数级别的时间复杂度,必须使用基于点的剖分[1]。每次找到树的重心[2]作为根节点,然后将根节点的子树平均分为两部分,两部分共用根节点。对每一部递归求解,然后把这两部分合并。求树的重心的方法是随便找一个根,求出每个子树的大小,找到max{i.child.size,N-i.size}最小的i,i就是树的重心。重心可能有多个,找一个即可。

对于一个分治的局面,每一部分都是当前根节点的一些子树组成的森林,再加上根节点,所以每一部分仍然是一棵树。最优的路径可能在某一个分治的部分中,也可能跨过根节点在两个部分中。前者可以直接递归下去求解,重点是处理后者的情况。这时需要做的一个重要转化是二分答案,由于答案的范围是已知的,我们可以在答案的范围内二分答案的值A,然后把树上每一条边的权值都减去A。判断有解的方法也就变成了判断是否存在一条带权长度大于等于0的路径,继续转化就是,判断最长的带权路径的带权长度是否大于等于0

如何找出跨两部分的最长带权路径呢?由于路径的长度必须满足在[L,U]之间,简单的想法是在一个部分中枚举路径的一个端点的深度i,那么这条路径的另一端在另一个部分中的深度一定是在[L-i,U-i]之间。为保证路径最长,第一个部分中深度为i的一段显然应该是这个部分中深度为i的所有路径中带权长度最大的那一条,第二部分也同理,不过要枚举深度在[L-i,U-i]的最大值。如果我们确定i的枚举顺序以后,[L-i,U-i]区间的移动就是单调的,因此可以用单调队列维护最大值,因此时间复杂度就是线性的。

算法描述

  1. 求出当前树的重心,对当前树进行点剖分。

  2. 二分当前树中平均长度最大值A,判断二分范围是否满足精度,如果满足转到步骤5,否则转到步骤3。

  3. 将树上所有边权值减去A,求出剖分的两部分每个深度上的最长带权路径长度。

  4. 用单调队列维护,求出跨两部分的带权路径长度最大值,判断该值是否大于等于0,转到步骤2。

  5. 对剖分的两部分分别递归求解,如果这一部分大小大于等于L的话。

复杂度分析

对树点剖分的时间复杂度为O(logN),求重心的时间复杂度为O(N),二分答案时间复杂度为O(logV),求带权路径长度最大值时间复杂度为O(N),因此总时间复杂度为O(NlogNlogV)。

参考程序

/* 
 * Problem: NOI Winter Camp 2010 Rebuild
 * Author: Guo Jiabao
 * Time: 2010.3.12 14:01
 * Label: Solved
 * Memo: Binary Search + Monoqueue + Devide & Conquer on tree
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <deque>
#include <string>
#include <queue>
using namespace std;
#define var(a,b) typeof(b) a(b)
#define foreach(a,b) for (var(a,b.begin());a!=b.end();++a)

const int MAXN = 100001,MAXM=MAXN*2,INF=~0U>>1;
const double LIM=1e6,FINF = 1e20;

struct Monoqueue
{
    struct element
    {
        int key;
        double value;
    }Q[MAXN];
    int head,rear;
    void reset()
    {
        rear = 0;
        head = 1;
    }
    void insert(int k,double v)
    {
        while (rear >= head && v > Q[rear].value)
            rear--;
        Q[++rear].value = v;
        Q[rear].key = k;
    }
    int getmax(int L)
    {
        while (Q[head].key < L)
            head++;
        return Q[head].key;
    }
}MQ;

struct edge
{
    edge *next;
    int t,c;
};

int N,L,U,EC,timestamp,Total;
int t_ctd,t_ctd_csm,md1,md2,*t_maxdpt;
int size[MAXN],depth[MAXN];
double length[MAXN],d1m[MAXN],d2m[MAXN],*t_dm;
edge *V[MAXN],ES[MAXM];
int ava[MAXN];
double Ans,t_delta;

inline void addedge(int a,int b,int c)
{
    edge *e=ES+ ++EC;
    e->next = V[a];
    e->t = b;
    e->c = c;
    V[a] = e;
}

void init()
{
    freopen("rebuild.in","r",stdin);
    freopen("rebuild.out","w",stdout);
    scanf("%d%d%d",&N,&L,&U);
    for (int i=1;i<N;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
        addedge(b,a,c);
        if (L == 1 && c > Ans)
            Ans = c;
    }
}

void get_depth(int i)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (depth[j] == -1)
        {
            depth[j] = depth[i] + 1;
            get_depth(j);
        }
    }
}

int get_longest_line(int start)
{
    int i,maxdepth;
    memset(depth,-1,sizeof(depth));
    depth[start] = maxdepth = 0;
    get_depth(start);
    for (i=1;i<=N;i++)
        if (ava[i] == 0 && depth[i] > maxdepth)
        {
            maxdepth = depth[i];
            start = i;
        }
    memset(depth,-1,sizeof(depth));
    depth[start] = maxdepth = 0;
    get_depth(start);
    for (i=1;i<=N;i++)
        if (ava[i] == 0 && depth[i] > maxdepth)
            maxdepth = depth[i];
    return maxdepth;
}

void get_size(int i)
{
    int csm = 0;
    size[i] = 1;
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (size[j] == -1)
        {
            get_size(j);
            size[i] += size[j];
            if (size[j] > csm)
                csm = size[j];
        }
    }
    if (Total - size[i] > csm)
        csm = Total - size[i];
    if (csm < t_ctd_csm)
    {
        t_ctd_csm = csm;
        t_ctd = i;
    }
}

int get_centroid(int i)
{
    memset(size,-1,sizeof(size));
    t_ctd_csm = INF;
    get_size(i);
    memset(size,-1,sizeof(size));
    return t_ctd;
}

void count_size(int i)
{
    size[i] = 1;
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        if (size[j] == -1)
        {
            count_size(j);
            size[i] += size[j];
        }
    }
}

void count_depth_max_length(int i)
{
    //求最大深度
    if (depth[i] > *t_maxdpt)
        *t_maxdpt = depth[i];
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (ava[j] != 0) continue;
        //求該深度最大帶權長度
        if (length[i] > t_dm[depth[i]])
            t_dm[depth[i]] = length[i];
        if (depth[j] == -1)
        {
            length[j] = length[i] + e->c - t_delta;
            depth[j] = depth[i] + 1;
            count_depth_max_length(j);
        }
    }
}

bool check(double delta,int ctd,edge *f)
{
    edge *e;
    int i,j,k;
    for (i=0;i<=N;i++)
        d1m[i] = d2m[i] = -FINF;
    t_delta = delta;
    memset(depth,-1,sizeof(depth));
    memset(length,-1,sizeof(length));
    md1 = md2 = 0;
    length[ctd] = depth[ctd] = 0;

    //統計部份1
    t_dm = d1m;
    t_maxdpt = &md1;
    for (e=V[ctd];e != f;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        length[j] = e->c - t_delta;
        depth[j] = 1;
        count_depth_max_length(j);
    }
    //統計部份2
    t_dm = d2m;
    t_maxdpt = &md2;
    for (e=f;e;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        length[j] = e->c - t_delta;
        depth[j] = 1;
        count_depth_max_length(j);
    }
    //單調隊列維護最大值
    //確定左邊界
    i = U-1;
    if (i > md1)
        i = md1;
    //確定右邊界
    k = L-i;
    if (k < 1)
        k = 1;
    MQ.reset();
    for (j=k;j<U-i && j<=md2 ;j++)
        MQ.insert(j,d2m[j]);
    double curv,maxv=-INF;
    for (;i>0 && L-i<=md2;i--)
    {
        j = U-i;
        if (j<=md2)
            MQ.insert(j,d2m[j]);
        int k = MQ.getmax(L-i);
        curv = d1m[i] + d2m[k];
        if (curv > maxv)
            maxv = curv;
    }
    return maxv >= 0;
}

double binary(int ctd,edge *f)
{
    double a=0,b=LIM,m;
    while (b - a >= 0.0001)
    {
        m = (a+b)/2;
        if (check(m,ctd,f))
            a = m;
        else
            b = m;
    }
    return a;
}

void dct(int start)
{
    int nowt = ++timestamp;
    int line = get_longest_line(start);
    if (line<=L || line<=2)
        return;
    int ctd = get_centroid(start); //取得重心
    double cur;
    //分割兩部份
    count_size(ctd);
    int pls = 0,pls2 = 0;
    edge *e,*f;
    for (e=V[ctd];e;e=e->next)
    {
        int j=e->t;
        if (ava[j] !=0) continue;
        pls += size[j];
        if (pls + pls + 1 >= size[ctd] - 1)
        {
            f = e->next;
            pls2 = size[ctd] - pls;
            pls++;
            break;
        }
    }
    //合併兩部份
    cur = binary(ctd,f);
    if (cur > Ans)
        Ans = cur;
    //遞歸部份1
    int j;
    if (pls-1 >= L)
    {
        for (e=f;e;e=e->next)
            if (ava[j=e->t] ==0)
                ava[j] = nowt;
        Total = pls;
        dct(ctd);
        for (edge *e=f;e;e=e->next)
            if (ava[j=e->t] ==nowt)
                ava[j] = 0;
    }
    //遞歸部份2
    if (pls2-1 >= L)
    {
        for (e=V[ctd];e!=f;e=e->next)
            if (ava[j=e->t] ==0)
                ava[j] = nowt;
        Total = pls2;
        dct(ctd);
        for (e=V[ctd];e!=f;e=e->next)
            if (ava[j=e->t] ==nowt)
                ava[j] = 0;
    }
}

void solve()
{
    memset(ava,0,sizeof(ava));
    Total = N;
    dct(1);
}

int main()
{
    init();
    solve();
    printf("%.3lf\n",Ans);
    return 0;
}

</>[1] 具体证明参见2009年集训队论文《分治算法在树的路径问题中的应用》。

[2] 树的重心就是满足“删除该点后,剩余的最大的子树顶点数最少”的点。

Related posts