BZOJ 1999 - [Noip2007]Core树网的核

#图论 #单调队列 #树上最长链 #NOIP
Published on 2016-11-04

题目地址

描述

给定一棵具有 n(n≤5⋅105)n(n\le 5\cdot{10}^5) 个节点的树，每条边 ii 带有权值 wiw_i，且满足 wi≤500w_i\le 500。
定义点 uu 到路径 PP 的距离 D(u,P)=minv∈Pd(u,v)D(u, P) = \min_{v\in P}d(u, v)。
定义路径 PP 的偏心距 ECC(P)=maxu∈VD(u,P)ECC(P) = \max_{u\in V}D(u, P)。
你需要找到一条在树的直径上的路径，满足其路径长度小于 s(s≤231−1)s(s\le 2^{31}- 1) 且偏心距最小。

分析

一棵树可能有多个直径，最坏可能有 O(n2)O(n^2) 条直径（菊花图），我们考虑是否只需要考虑其中的任意一条直径。不失一般性，我们考虑只有两条直径的情况，这两条直径必然是相交的，如图：

我们可以证明，∣AE∣=∣CE∣\vert AE\vert = \vert CE\vert 且 ∣BF∣=∣DF∣\vert BF \vert= \vert DF\vert。现在就证明在任意路径上选取 PP 是等价的：

假设 PP 没有能覆盖 EFEF，那么偏心距就是直径未被覆盖的部分较长的那一段，这一段的长度只与直径的长度有关系，所以等价。
假设 PP 覆盖 EFEF，且 PP 在 ABAB 上，此时偏心矩是 max(∣CE∣,∣DF∣,Val)\max(\vert CE\vert, \vert DF\vert, \text{Val})，其中 Val\mathrm{Val} 是 EFEF 上的点向下延伸的最长链，这个值也与 PP 在哪条直径上无关。而如果 PP 在 CDCD 上，此时偏心矩是 max(∣BF∣,∣DF∣,Val)\max(\vert BF \vert, \vert DF\vert, \mathrm{Val})，与在 ABAB 上的偏心距是相等的，所以等价。

剩下的问题就变成了在任意一个直径上找一个区间 [l,r][l, r]，满足偏心距最小且长度小于 ss，由于 [l,r+1][l, r +1] 的答案一定不大于 [l,r][l, r] 的答案，所以我们对每一个 ii 求出一个最大的区间 [i,j)[i, j)，记录一下前缀后缀最大值以及 [i,j)[i, j) 中向下最长的链（用单调队列维护），就可以 O(n)O(n) 求解了。这些都是基本功以及常用技巧了，如果不会，看代码研究吧。

代码

//  Created by Sengxian on 2016/11/03.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1999 树的直径 + DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 500000 + 3;
struct edge {
    edge *next;
    int to, cost;
    edge(edge *next = NULL, int to = 0, int cost = 0): next(next), to(to), cost(cost) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];

int n, s, dis[MAX_N], fa[MAX_N], q[MAX_N];
bool in_diameter[MAX_N];

int Dfs(int st) {
    int l = 0, r = 0, mx = st;
    q[r++] = st, fa[st] = -1, dis[st] = 0;
    while (r - l >= 1) {
        int u = q[l++];
        if (dis[u] > dis[mx]) mx = u;
        for (edge *e = first[u]; e; e = e->next) if (e->to != fa[u] && !in_diameter[e->to]) {
            dis[e->to] = dis[u] + e->cost;
            fa[e->to] = u;
            q[r++] = e->to;
        }
    }
    return mx;
}

void solve(int u, int v) {
    static int nodes[MAX_N], d[MAX_N], dp[MAX_N], f[MAX_N], g[MAX_N];
    int len = 0;
    for (int cur = v; cur != -1; cur = fa[cur]) nodes[len++] = cur, in_diameter[cur] = true;
    for (int i = 1; i < len; ++i) d[i] = dis[nodes[i - 1]] - dis[nodes[i]] + d[i - 1];
    for (int i = 0; i < len; ++i) dp[i] = dis[Dfs(nodes[i])];

    f[0] = dp[0];
    for (int i = 1; i < len; ++i) f[i] = max(f[i - 1] + d[i] - d[i - 1], dp[i]);
    g[len - 1] = dp[len - 1];
    for (int i = len - 2; i >= 0; --i) g[i] = max(g[i + 1] + d[i + 1] - d[i], dp[i]);

    int l = 0, r = 0, ans = INT_MAX;
    for (int i = 0, j = 0; i < len; ++i) {
        if (q[l] == i - 1) l++;
        while (j < len && d[j] - d[i] <= s) {
            while (r - l >= 1 && dp[q[r - 1]] <= dp[j]) r--;
            q[r++] = j++;
        }
        ans = min(ans, max(max(f[i], g[j - 1]), dp[q[l]]));
    }
    printf("%d\n", ans);
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), s = ReadInt();
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        u = ReadInt() - 1, v = ReadInt() - 1, w = ReadInt();
        first[u] = new (pit++) edge(first[u], v, w);
        first[v] = new (pit++) edge(first[v], u, w);
    }
    int u = Dfs(0), v = Dfs(u);
    solve(u, v);    
    return 0;
}
「NOIP 2008」双栈排序