This page looks best with JavaScript enabled

「SDOI2011」消防-树的直径+单调队列

 ·  ✏️ About  731 words  ·  ☕ 2 mins read · 👀... views

某个国家有 $n$ 个城市,这 $n$ 个点之间的边构成一棵树。

现求一条边长度和不超过 $S$ 的路径(两端都是城市,可以只为一个城市),使得所有城市到这条路径的距离的最大值最小,并输出这个最小值。

链接

Luogu P2491

题解

很有趣的题。

很明显,这条路径必须全部位于直径上。具体证明不会,大概可以感性理解一下。

那么我们就要考虑,在直径上选出一段长度不大于 $S$ 的路径,如何维护这颗树上的所有点到这条路径的长度的最大值。

考虑到只有两种情况:

  • 在树的直径上叉出来的一支
  • 路径上的两个端点到同侧直径端点的距离

第一个先 $O(n)$ 预处理出来,第二个记录直径的一个端点到直径上所有点的距离,然后可以 $O(1)$ 的计算。

我们枚举路径的右端点 $r$ ,然后把左端点 $l$ 推到最左侧可以满足 $d \leq S$ 的点,这个过程是 $O(n)$ 的,注意到 $l,r$ 都是单调递增的,我们可以用一个单调队列维护 $[l,r]$ 的最大值,然后再与第二个情况取一个 $max$ 。然后最小值就是我们的 $ans$ 。

总时间复杂度 $O(n)$ 。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cctype>
#define pp pair<int,int>
using namespace std;

namespace fast_io {
    //...
}using namespace fast_io;

const int MAXN = 310000;

struct Edge{
    int from,to;
    int len;
};

int n,k;
vector<Edge> edge[MAXN];

void init(){
    read(n),read(k);
    int a,b,c;
    for(int i = 1;i<=n-1;i++){
        read(a),read(b),read(c);
        edge[a].push_back((Edge){a,b,c});
        edge[b].push_back((Edge){b,a,c});
    }
}

int dis[MAXN],f[MAXN];

void dfs(int nown,int fa){
    f[nown] = fa;
    for(int i = 0;i<edge[nown].size();i++){
        int v = edge[nown][i].to,l = edge[nown][i].len;
        if(v == f[nown]) continue;
        dis[v] = dis[nown] + l;
        dfs(v,nown);
    }
}

int getmax(int nown){
    int ans = dis[nown];
    for(int i = 0;i<edge[nown].size();i++){
        int v = edge[nown][i].to;
        if(v == f[nown]) continue; 
        ans = max(ans,getmax(v));
    }
    return ans;
}

int num[MAXN],d[MAXN],maxn[MAXN],tot = 0;

void build(){
    int u = 0,v = 0;
    dis[1] = 0;
    dfs(1,0);
    for(int i = 1;i<=n;i++)
        if(dis[u] < dis[i]) u = i;
    dis[u] = 0;
    dfs(u,0);
    for(int i = 1;i<=n;i++)
        if(dis[v] < dis[i]) v = i;
    for(int i = v;i;i = f[i])
        num[++tot] = i;
    reverse(num+1,num+tot+1);
    for(int i = 1;i<=tot;i++)
        d[i] = dis[num[i]];
    for(int i = 1;i<=tot;i++){
        int nown = num[i];
        for(int j = 0;j<edge[nown].size();j++){
            int v = edge[nown][j].to;
            if(v == num[i+1] || v == num[i-1]) continue;
            maxn[i] = max(maxn[i],getmax(v));
        }
        if(maxn[i]) maxn[i] -= d[i];
    }
}

void solve(){
    deque<pp> q;
    int l = 1,ans = 0x3f3f3f3f;
    
    for(int i = 1;i<=tot;i++){
        while(!q.empty() && q.back().second < maxn[i])
            q.pop_back();
        q.push_back(make_pair(i,maxn[i]));
        while(d[i] - d[l] > k)
            l++;
        while(!q.empty() && q.front().first < l)
            q.pop_front();
        ans = min(ans,max(max(d[l],d[tot] - d[i]),q.front().second));
    }
    printf("%d\n",ans);
}

int main(){
    init();
    build();
    solve();
    flush();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: