链接

LuoguP2680

题解

首先求出给定的这些路径边权和，的时候预处理出每个点到根节点的路径的边权和，用表示。用倍增求出给定路径端点的最近公共祖先，用表示路径端点，表示最近公共祖先，那么这些路径的长度就是

然后对这些路径按照边权和，以递减的顺序排序。然后二分答案。其单调性体现在，答案越小，这条边权将要变成的边的边权就要越大，就要被更多的路径所包含。对于所有边权和大于答案的路径，当且仅当边权将要修改的那条边被这些路径都包含，答案才有成立的可能。当满足上一个条件，并且边权和最大的路径的边权减去这条边的边权小于或等于答案时，这个答案就是成立的。

怎么求这些路径的公共部分呢？

如果你能联想到序列的话，就不难想到可以使用差分来求。可以把树上的路径拆分成两条链来看。对于树上的每个点，这个点的标记表示的是连接该点与其父节点的边的标记，因为边不容易检索与维护。然后对其子树递归求和即可。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

const int MAXN = 3e5 + 7;

struct Edge {
    int s, t, w, next;
} edge[MAXN << 1];

struct Path {
    int x, y, lca, len;

    bool operator < (const Path &x) const {
        return this->len > x.len;
    }
} p[MAXN];

int cnt, head[MAXN], dif[MAXN], f[MAXN][22], deep[MAXN], sum[MAXN], max;
int n, m, num;
int l = 0, r = -2147483647;

void read(int &x) {
    int flag = 1, ret = 0;
    x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    x = ret * flag;
}

void add(int u, int v, int w) {
    cnt++;
    edge[cnt].s = u;
    edge[cnt].t = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u, int pre) {
    f[u][0] = pre;
    deep[u] = deep[pre] + 1;

    for (int i = 1; i <= 21 && deep[u] - (1 << i) >= 1; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }

    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        sum[v] = sum[u] + edge[e].w;
        dfs(v, u);
    }
}

int Lca(int a, int b) {
    if (deep[a] > deep[b]) std::swap(a, b);

    for (int i = 21; i >= 0; i--) {
        if (deep[f[b][i]] >= deep[a]) b = f[b][i];
    }

    if (a == b) return a;

    for (int i = 21; i >= 0; i--) {
        if (f[a][i] == f[b][i]) continue;
        a = f[a][i];
        b = f[b][i];
    }
    return f[a][0];
}

void dfs2(int u, int pre) {
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        dfs2(v, u);
        dif[u] += dif[v];
    }
    if (dif[u] == num) max = std::max(max, sum[u] - sum[f[u][0]]);
}


bool check(int mid){
    memset(dif, 0, sizeof(dif));
    num = 0;
    max = -2147483647;
    for (int i = 1; i <= m && p[i].len > mid; i++) {
        num++;
        dif[p[i].x]++;
        dif[p[i].y]++;
        dif[p[i].lca] -= 2;
    }
    dfs2(1, 0);
    if (max == -2147483647 || p[1].len - max > mid) {
        return false;
    }
    return true;
}

int binarySearch() {
    int mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main(int argc, char *argv[]) {
    read(n), read(m);

    int u, v, w;
    for (int i = 1; i < n; i++) {
        read(u), read(v), read(w);
        add(u, v, w);
        add(v, u, w);
    }

    dfs(1, 0);

    for (int i = 1; i <= m; i++) {
        read(p[i].x), read(p[i].y);
        p[i].lca = Lca(p[i].x, p[i].y);
        p[i].len = sum[p[i].x] + sum[p[i].y] - sum[p[i].lca] * 2;
        r = std::max(r, p[i].len);
    }
    std::sort(p + 1, p + m + 1);
    int ans = binarySearch();
    printf("%d\n", ans);
    return 0;
}