BZOJ 1999 树网的核[数据加强版] 树的直径+线段树

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

此题原本是NOIP提高组一道压轴,这一改数据感觉可以放省选赛或者CCPC难题里面什么的了

鬼知道为什么我当初做这道题会YY出线段树做法,现在想想我自己都佩服我自己。

嘛写这篇算是权当复习一下思路了。

题目告诉我们最小偏心距是什么了……我们要求的就是选定一个长度不超过s的核(在直径上,也可以是点也可以是边)使得离这个核最远的点离这个核 的距离最小。

首先求直径是很好求的,两遍BFS就搞定了。

但是直径可能会有很多条,那我们就对每一条都要计算。

对于每一条直径,我们的答案一定是由两类值的最大值来组成:

1.非此直径上的点到当前选定的核的距离的最大值。

2.直径的两个端点到当前选定的核的距离的最大值。

我们考虑用两个指针(two-pointers)的思想,不断的在直径上移动我们选定的核的两端(保证长度不超过s),这样可以保证线性查询,而不是暴力枚举带来的平方复杂度的查询。

距离直径的两个端点的值很好求,只需要在移动指针的时候不断地修改就可以了。

至于非此直径上的点,我们可以预处理他们到每一个此直径上的点的距离的最大值,然后再不断移动核的两端的时候,我们发现,这其实就是求当前核所涵盖的区间上的点的最远距离的最大值,这个区间问题我们可以用线段树(或者树状数组)进行查询,这样就可以logn的复杂度内查询了。

对于每一条直径我们都这么操作来算出一个答案,最终取所有答案的最小值就是最小偏心距了。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
int get_num() {
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if (c == '-')
        flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 500005;
struct edge {
    int to, next, v;
}e[maxn << 1];
int h[maxn], dis[maxn], pre[maxn], fa[maxn], mdis[maxn], qz[maxn];
bool vis[maxn];
int ax[maxn];
int n, k, st, en, cnt = 0;
int mx = 0, pos, now = 0;
struct seg {
    int l, r, val;
}tr[maxn<<2];
void push_up(int now) {
    tr[now].val = max(tr[now << 1 | 1].val, tr[now << 1].val);
    return;
}
void build(int now, int l, int r) {
    tr[now].l = l;
    tr[now].r = r;
    if (l == r) {
        tr[now].val = mdis[ax[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(now << 1, l, mid);
    build(now << 1 | 1, mid + 1, r);
    push_up(now);
    return;
}
int query(int now, int l, int r) {
    if (tr[now].l >= l && tr[now].r <= r)
        return tr[now].val;
    int mid = (tr[now].l + tr[now].r) >> 1;
    int ans = 0;
    if (l <= mid)ans = max(ans, query(now << 1, l, r));
    if (r > mid)ans = max(ans, query(now << 1 | 1, l, r));
    return ans;
}
void init() {
    memset(dis, 0, sizeof(dis));
    memset(e, 0, sizeof(e));
    memset(h, -1, sizeof(h));
    memset(ax, 0, sizeof(ax));
    memset(vis, 0, sizeof(vis));
    return;
}
void BFS(int s, int b) {
    dis[s] = 0;
    fa[s] = s;
    queue<int>q;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = h[x]; i != -1; i = e[i].next) {
            if (dis[e[i].to] != 0 || e[i].to == s)continue;
            dis[e[i].to] = dis[x] + e[i].v;
            if (b == 1) {
                pre[e[i].to] = e[i].v;
                fa[e[i].to] = x;
            }
            if (mx <= dis[e[i].to]) {
                pos = e[i].to;
                mx = dis[e[i].to];
            }
            q.push(e[i].to);
        }
    }
    return;
}
void DFS(int s, int top) {
    dis[top] = 0;
    for (int i = h[s]; i != -1; i = e[i].next) {
        if (vis[e[i].to])continue;
        if (dis[e[i].to] != 0)continue;
        dis[e[i].to] = dis[s] + e[i].v;
        mdis[top] = max(mdis[top], dis[e[i].to]);
        DFS(e[i].to, top);
    }
    return;
}
void add(int a, int b, int c) {
    e[now].to = b; e[now].v = c;
    e[now].next = h[a]; h[a] = now++;
    return;
}
int p[maxn],op = 0; 
int main() {
    n = get_num();
    k = get_num();
    int a, b, c;
    init();
    for (int i = 1; i < n; ++i) {
        a = get_num();
        b = get_num();
        c = get_num();
        add(a, b, c);
        add(b, a, c);
    }
    BFS(1, 0);
    st = pos;
    mx = 0;
    int ansp = INF;
    for(int i = 1;i <= n;++i)dis[i] = 0;
    BFS(pos, 1);
    for(int i = 1;i <= n;++i){
        if(dis[i] == mx)p[++op] = i;
    }
    for(int g = 1;g <= op;++g){
        en = p[g];
        int x = en;
        for(int i = 1;i <= n;++i){
            mdis[i] = 0;
            ax[i] = 0;
            vis[i] = false;
            qz[i] = 0;
        }
        while (fa[x] != x) {
            ax[++cnt] = x;
            vis[x] = true;
            x = fa[x];
        }
        ax[++cnt] = st;
        vis[st] = true;
        qz[1] = 0;
        for(int i = 1;i <= n;++i)dis[i] = 0;
        for (int i = 1; i <= cnt; ++i) {
            DFS(ax[i], ax[i]);
            if (i >= 2)qz[i] = qz[i - 1] + pre[ax[i-1]];
        }
        int i = 1, j = 1, ansx = 0;
        build(1, 1, cnt);
        while (j < cnt) {
            while (qz[j+1] - qz[i]  <= k){
                j++;
                if(j == cnt)break;
            } 
            ansx = max(query(1,i,j),qz[i] - qz[1]);
            ansx = max(ansx,qz[cnt] - qz[j]);
            ansp = min(ansp, ansx);
            ++i;
            if(i > j)j = i; 
        }
    }
    printf("%d\n", ansp);
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00