NOIP2015运输计划（树上前缀和+LCA+二分）

Description

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

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

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

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

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

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

Input Format

第一行包括两个正整数 n,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 1 到 n 编号。

接下来 n−1 行描述航道的建设情况，其中第 i 行包含三个整数 ai,bi 和 ti，表示第 i 条双向航道修建在 ai 与 bi 两个星球之间，任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。

接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n

Output Format

输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

Sample Input

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

Sample Output

11

Hint

将第 1 条航道改造成虫洞： 则三个计划耗时分别为：11,12,11，故需要花费的时间为 12。

将第 2 条航道改造成虫洞： 则三个计划耗时分别为：7,15,11，故需要花费的时间为 15。

将第 3 条航道改造成虫洞： 则三个计划耗时分别为：4,8,11，故需要花费的时间为 11。

将第 4 条航道改造成虫洞： 则三个计划耗时分别为：11,15,5，故需要花费的时间为 15。

将第 5 条航道改造成虫洞： 则三个计划耗时分别为：11,10,6，故需要花费的时间为 11。

故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短，需要花费的时间为 11。

n,m<=300000

Solution

先分析一下题目，n个点n-1条边且图联通，明显是树结构，

不难发现，题目是求最大值最小，不妨用二分答案

那么如何验证呢，对于每个计划，检查是否存在一些不合法线路，即两点间最短距离>mid，那么显然我们要选一条边作为虫洞，而且是所有不合法线路都经过的边

我们开一个数组sum[i]表示编号为i的边被多少条线路覆盖，那么对于所有不合法线路都经过的边，找一个最长的一条，把它设为虫洞，为最优

那么关键在于如何维护数组sum

经过shawn_xc学长的指导，用树上前缀和可以解决，

当发现一条不合法路径u to v时，令sum[u]++,sum[v]++,sum[lca(u,v)]-=2

因为后面要求前缀和，就令sum[lca(u,v)]-=2，加上其子节点的sum和就抵消了，很巧妙

最后就判断一下满足即可被所以不合法路线经过的边中最长的边设为虫洞后是否可行即可

Code

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 300010
using namespace std;

struct plan
{
    int u, v, lca, dis;
} node[N];
struct info {
    int to, nex, w;
} e[N * 2];
int n, m, head[N * 2], tot;
int l, r, edge[N];
bool vis[N];
int _log, fa[N][19], dep[N], dis[N];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

inline void add_edge(int u, int v, int w) {
    e[++tot].to = v;
    e[tot].w = w;
    e[tot].nex = head[u];
    head[u] = tot;
}

void dfs(int u) {
    vis[u] = 1;

    for (int i = 1; i <= _log; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].to;
        if (vis[v]) continue;
        edge[v] = i;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;
        dis[v] = dis[u] + e[i].w;
        dfs(v);
    }
}

int LCA(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    int d = dep[v] - dep[u];

    for (int i = 0; i <= _log; ++i)
        if (d & (1 << i))
            v = fa[v][i];

    if (u == v) return u;

    for (int i = _log; i >= 0; i--)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }

    return fa[u][0];
}

int sum[N];
void update(int u, int fa) {
    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].to;
        if (v == fa) continue;
        update(v, u);
        sum[u] += sum[v];
    }
}

bool pd(int mid) {
    int tot = 0, dec = 0;
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= m; ++i)
        if (node[i].dis > mid) {
            tot++;
            dec = max(dec, node[i].dis - mid);
            sum[node[i].u]++;
            sum[node[i].v]++;
            sum[node[i].lca] -= 2;
        }
    update(1, 1);
    for (int i = 1; i <= n; ++i)
        if (sum[i] == tot && e[edge[i]].w >= dec) return 1;
    return 0;
}

int main() {
    n = read(), m = read();
    _log = log(n) / log(2);
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs(1);

    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        node[i].u = u, node[i].v = v;
        node[i].lca = LCA(u, v);
        node[i].dis = (dis[u] + dis[v]) - 2 * dis[node[i].lca];
        r = max(r, node[i].dis);
    }
    int Ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (pd(mid))
            Ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", Ans);
    return 0;
}