Chlience

【题解】BZOJ 1758 [WC2010]重建计划
Problem给定一棵树,求长度在 $[L,U]$ 之间的平均权值最大的一条简单路径Thought看到这个题,是不...
扫描右侧二维码阅读全文
03
2019/01

【题解】BZOJ 1758 [WC2010]重建计划

Problem

给定一棵树,求长度在 $[L,U]$ 之间的平均权值最大的一条简单路径

Thought

看到这个题,是不是想起了 [HNOI2009]最小圈 呢?

题目要求平均权值最大,那么二分答案没得跑了
如果是平均权值最大环,那就每条边权值减去 $mid$ 然后看是否有正环(反向跑副环)
同样,对于每个二分到的答案 $del$,将所有边权减去 $del$,那么问题转化为 是否 有一条长度在 $[L,U]$ 的总边权为正的简单路径

这个东西很明显可以使用点分治来维护,那就点分治裸题了呗

考虑合并子树的答案,由于总长度有限制,那么从小到大枚举当前子树选择的长度,前面子树的贡献的长度应该是一个不断向前滑动的窗口,使用单调队列维护下就行了

考虑滑动窗口的复杂度,因为其长度和前面子树的最长长度相关,在某些极限情况会被卡到 $N^2$
比如说 $1$ 个深度为 $n/2$ 的子树和 $n/2$ 个深度为 $1$ 的子树,若先处理深度为 $n/2$ 的子树,后面每个子树都需要遍历一遍 $1-n/2$,时间复杂度 $\frac{n^2}{4}$,即

$$ T(n)=aT(\frac{n}{a})+n^2 $$

时间复杂度为 $O(n^2)$ 级别

但是如果每次合并子树时从小到大合并,那么其总复杂度只和当前的子树大小相关

$$ T(n)=aT(\frac{n}{a})+n\log n $$

时间复杂度 $O(n\log^3 n)$

Tip: 因为这个题稍微有点卡常,尽量优化常数,比如说 预处理重心

卡了2h,重构三次的就是我了

Code

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-4
const int INF = 0x3f3f3f3f;
const int N = 100010;
#define mid ((l + r) / 2)
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct Edge {
    int t , n; double w;
    void add(int _t , int _n , double _w) {t = _t; n = _n; w = _w;}
}e[N << 1];
int head[N] , tot;
struct point {
    int node;
    double val;
    int len;
    bool operator < (const point x) const {return len < x.len;}
}p[N];
int siz[N] , len[N] , max_siz[N];
double f[N] , g[N];
double del , ANS;
double minkey = INF , maxkey = 0;
int n , D , U , root;
bool vis[N];
int flen , glen;
vector <int> RT[N];
deque <int> q;
void addedge(int u , int v , int w) {
    e[++ tot] = {v , head[u] , (double) w};
    head[u] = tot;
}
void init() {
    n = read(); D = read() ; U = read();
    for(int i = 1 ; i < n ; ++ i) {
        int u = read() , v = read() , w = read();
        addedge(u , v , w);
        addedge(v , u , w);
        minkey = min(minkey , (double) w);
        maxkey = max(maxkey , (double) w);
    }
}
void getRoot(int x , int fa , int sum_siz) {
    siz[x] = 1; max_siz[x] = 0;
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t]) {
            getRoot(e[i].t , x , sum_siz);
            siz[x] += siz[e[i].t];
            max_siz[x] = max(max_siz[x] , siz[e[i].t]);
        }
    max_siz[x] = max(max_siz[x] , sum_siz - siz[x]);
    if(!root || max_siz[x] < max_siz[root]) root = x;
}
void getLen(int x , int fa) {
    len[x] = 1; 
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t])
            len[x] = max(len[x] , len[e[i].t] + 1);
}
void getG(int x , int fa , int dep , double val) {
    if(dep > U) return;
    if(dep <= glen) g[dep] = max(g[dep] , val);
    else {g[glen = dep] = val;}
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t])
            getG(e[i].t , x , dep + 1 , val + e[i].w - del);
}
void dfs(int x) {
    vis[x] = 1;
    for(auto i = RT[x].begin() ; i != RT[x].end() ; ++ i) dfs(*i);
    flen = 0;
    int cnt = 0;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(vis[e[i].t]) continue;
        getLen(e[i].t , x);
        p[++ cnt] = {e[i].t , e[i].w - del , len[e[i].t]};
    }
    sort(p + 1 , p + cnt + 1);
    for(int i = 1 ; i <= cnt ; ++ i) {
        glen = 0;
        getG(p[i].node , x , 1 , p[i].val);
        while(!q.empty()) q.pop_back();
        for(int j = min(U , flen) ; j >= D ; -- j) {
            while(!q.empty() && f[q.back()] < f[j]) q.pop_back();
            q.push_back(j);
        }
        
        for(int j = 1 ; j <= glen ; ++ j) {
            if(!q.empty() && q.front() > U - j) q.pop_front();
            if(D - j >= 1 && D - j <= flen) {
                while(!q.empty() && f[q.back()] <= f[D - j]) q.pop_back();
                q.push_back(D - j);
            }
            if(!q.empty()) ANS = max(ANS , g[j] + f[q.front()]);
        }
        for(int j = 1 ; j <= glen ; ++ j)
            if(j <= flen) f[j] = max(f[j] , g[j]);
            else f[flen = j] = g[j];
    }
    for(int i = D ; i <= min(U , flen) ; ++ i)
        ANS = max(ANS , f[i]);
    vis[x] = 0;
}
bool check(int rt) {
    ANS = - INF;
    dfs(rt);
    return ANS >= 0;
}
void prework(int x , int S) {
    vis[x] = 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(vis[e[i].t]) continue;
        root = 0;
        getRoot(e[i].t , x , siz[e[i].t]);
        RT[x].push_back(root);
        prework(root , siz[e[i].t]);
    }
    vis[x] = 0; 
}
void work() {
    getRoot(1 , 0 , n);
    int rt = root;
    prework(rt , n);
    double l = minkey , r = maxkey , ans = 0;
    while(r - l > eps) {
        del = mid;
        if(check(rt)) {ans = mid; l = mid;}
        else r = mid;
    }
    printf("%.3lf\n" , ans);
}
int main() {
    init();
    work();
    return 0;
}
Last modification:January 3rd, 2019 at 10:55 am

Leave a Comment