算法

(LCA,树上差分,二分) $O((N+M)logT)$

如果可以在 $t$ 时间内完成，则一定可以在大于 $t$ 的时间内完成，因此可以二分答案。

时间确定之后，原问题变成一个判定性问题：是否可以通过去掉一条边，使所有路径的总长度在 $t$ 以内。

此时去掉所有长度大于 $t$ 的路径的最长公共边一定是最优的。

那怎么找出所有公共边呢？我们可以将每条路径上的所有边加1，最后判断每条边上的总和是否等于路径总数即可。

最后的问题是如何快速求树上某一条路径的和，以及给某个路径加上相同数呢？这里可以借鉴前缀和和差分的思想。在树上做前缀和和差分的时候需要先求路径两个端点的最近公共祖先，求LCA的方式有很多，这里采用的是倍增的方式。

时间复杂度

令 $N$ 表示总点数，$M$ 表示总边数，$T$ 表示路径长度的最大值。
那么预处理时使用倍增法求所有点对的最近公共祖先，时间复杂度是 $O(MlogN)$。
接下来会二分 $logT$ 次，每次判断需要 $O(N + M)$ 的时间，因此总时间复杂度是 $O((N+M)logT)$。

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 300010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], depth[N];
int f[N][20], seq[N], cnt;
int sum[N];
PII trans[N];
int blca[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int dep, int father)
{
    cnt ++ ;
    seq[cnt] = u;
    depth[u] = dep;

    for (int i = 1; i < 20; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            dist[j] = dist[u] + w[i];
            f[j][0] = u;
            dfs(j, dep + 1, u);
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    int d = depth[x] - depth[y];
    for (int i = 0; i < 20; i ++ )
        if (d >> i & 1)
            x = f[x][i];
    if (x == y) return x;

    for (int i = 19; i >= 0; i -- )
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    return f[x][0];
}

bool check(int mid)
{
    memset(sum, 0, sizeof sum);
    int maxd = 0, s = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int x = trans[i].first, y = trans[i].second;
        int p = blca[i];
        int d = dist[x] + dist[y] - dist[p] * 2;
        if (d > mid)
        {
            sum[x] += 1, sum[y] += 1;
            sum[p] -= 2;
            maxd = max(maxd, d - mid);
            s ++ ;
        }
    }

    if (!s) return true;

    for (int i = n; i; i -- )
    {
        int x = seq[i];
        sum[f[x][0]] += sum[x];
    }
    for (int i = 1; i <= n; i ++ )
        if (sum[i] == s && dist[i] - dist[f[i][0]] >= maxd)
            return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, 0, -1);

    for (int i = 1; i <= m; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        trans[i] = {x, y};
        blca[i] = lca(x, y);
    }

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

    printf("%d\n", r);
    return 0;
}