「NOIP2015」运输计划 - 二分答案 + 最近公共祖先 + 树上差分

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

公元 \(2044\) 年，人类进入了宇宙纪元。

L 国有 \(n\) 个星球，还有 \(n - 1\) 条双向航道，每条航道建立在两个星球之间，这 \(n - 1\) 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 \(u_i\) 号星球沿最快的宇航路径飞行到 \(v_i\) 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 \(j\)，任意飞船驶过它所花费的时间为 \(t_j\)，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新，L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 \(m\) 个运输计划。在虫洞建设完成后，这 \(m\) 个运输计划会同时开始，所有飞船一起出发。当这 \(m\) 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

解题思路

本题实质上是将一棵树中的一条边的权值设为 \(0\)，使 \(m\) 条最大路径长度最小。显然可以想到二分答案。

我们可以二分最长路径的长度。设最长长度为 \(\text{limit}\)，我们可以得出：对于所有长度大于 \(\text{limit}\) 的路径，我们必须删去这些路径的最长公共边。判断删去这条公共边后所有路径长度是否小于 \(\text{limit}\)，这样不停二分出答案即可。

但直接找出公共边的时间复杂度过高，又由于这是一颗树，于是我们可以用 LCA + 树上差分解决。对于一条路径，我们可以在其两端点标记 \(+1\)，在两端点的 LCA 标记 \(-2\)，最后树上求前缀和，边上标记数即代表了这是多少条路径的公共边。

代码演示

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 300000;
const int LOG_MAXN = 19;

struct Node {
    std::vector<struct Edge> e;
    struct Edge *in;
    Node *f[LOG_MAXN + 1], *p;
    int d, sum, mark;
} N[MAXN + 1];

struct Edge {
    Node *s, *t;
    int w, mark;

    Edge(Node *s, Node *t, int w) : s(s), t(t), w(w) {}
} *E[MAXN + 1];

struct Path {
    Node *u, *v, *p;
    int dist;
} P[MAXN + 1];

int n, m;
Node *tasks[MAXN + 1][2];
int maxDist;

inline void addEdge(int s, int t, int w) {
    N[s].e.push_back(Edge(&N[s], &N[t], w));
    N[t].e.push_back(Edge(&N[t], &N[s], w));
}

void prepare(Node *v, Node *f = NULL) {
    v->f[0] = v->p = f;
    v->d = (f ? f->d : 0) + 1;
    for (int i = 1; i <= LOG_MAXN; i++) {
        if (v->f[i - 1]) {
            v->f[i] = v->f[i - 1]->f[i - 1];
        }
    }
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t == f) continue;
        e->t->sum += e->w + e->s->sum;
        e->t->in = e;
        prepare(e->t, v);
    }
}

inline Node *lca(Node *u, Node *v) {
    if (u->d < v->d) std::swap(u, v);
    if (u->d != v->d) {
        for (int i = LOG_MAXN; i >= 0; i--) {
            if (u->f[i] && u->f[i]->d >= v->d) {
                u = u->f[i];
            }
        }
    }
    if (u != v) {
        for (int i = LOG_MAXN; i >= 0; i--) {
            if (u->f[i] != v->f[i]) {
                u = u->f[i];
                v = v->f[i];
            }
        }
        return u->p;
    }
    return u;
}

inline int dist(Node *u, Node *v, Node *p) {
    return u->sum + v->sum - 2 * p->sum;
}

void calcSum(Node *v, Node *p = NULL) {
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t == p) continue;
        calcSum(e->t, v);
        v->mark += e->t->mark;
    }
    if (v->in) v->in->mark += v->mark;
}

bool check(int limit) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) N[i].mark = 0;
    for (int i = 2; i <= n; i++) E[i]->mark = 0;

    for (int i = 1; i <= m; i++) {
        if (P[i].dist > limit) {
            cnt++;
            P[i].u->mark++;
            P[i].v->mark++;
            P[i].p->mark -= 2;
        }
    }

    calcSum(&N[1]);

    Edge *maxEdge = NULL;
    for (int i = 2; i <= n; i++) {
        if (E[i]->mark == cnt && (!maxEdge || E[i]->w > maxEdge->w)) {
            maxEdge = E[i];
        }
    }

    return maxEdge && maxDist - maxEdge->w <= limit;
}

int main() {
    scanf("%d %d", &n, &m);

    maxDist = 0;
    for (int i = 1; i <= n - 1; i++) {
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        addEdge(a, b, t);
    }

    prepare(&N[1]);
    for (int i = 2; i <= n; i++) E[i] = N[i].in;

    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        P[i].u = &N[u], P[i].v = &N[v];
        P[i].p = lca(P[i].u, P[i].v);
        P[i].dist = dist(P[i].u, P[i].v, P[i].p);
        maxDist = std::max(maxDist, P[i].dist);
    }

    int l = 0, r = maxDist;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", l);

    return 0;
}