题解

题目类型：树上二分答案 + LCA + 差分统计
核心目标：给定一棵带权树与 m 条路径，允许把至多一条边的权值下调（不小于 0），求能使所有这 m 条路径长度的最大值尽量小——输出该最小可能的最大值。

直观理解：我们想把“最吃亏”的那批路径一把“拉低”。只有一次机会下调某条边的权值，如果这条边恰好被所有“超标路径”同时经过，那么统一把它减去同样的值，就能让它们一起回到阈值以内。

一、预处理与基础公式

• 任选 1 为根，DFS 预处理：
  • fa[v][0]：父节点；
  • a[v]：(fa[v], v) 这条边的权值；
  • dep[v]：深度；
  • sum[v]：根到 v 的距离。
• 倍增 LCA：fa[v][j] = fa[fa[v][j-1]][j-1]。
• 任意两点路径长度： [ \text{dist}(x,y)=\text{sum}[x]+\text{sum}[y]-2\cdot \text{sum}[\text{lca}(x,y)] ]

读入 m 条询问 (x_i, y_i)，并计算：

• b[i].t = lca(x_i,y_i)
• b[i].val = dist(x_i,y_i)
  同时记录所有路径的最大长度 mx1；所有边（即父边）的最大权值 mx2。

二、判定函数 check(x) 的含义

问题转化：判断是否存在一条边，把它的权值统一减少 Δ≥0，使所有路径长度都 ≤ x。

• 把超过阈值 x 的路径称为坏路径。
  对每条坏路径，我们需要至少把它的长度减少
  [ \text{need}_i = \text{val}_i - x ]
• 若想一次减法解决所有坏路径，必须找出一条被所有坏路径都经过的边，并且这条边的权值 ≥ max(need_i)，记作 mx。

如何快速找“被所有坏路径同时经过”的边？

对每条坏路径 (x,y) 做树上差分：

• s[x]++，s[y]++，s[lca]-=2
• 最后一次自底向上的 DFS 累和：s[u] += Σ s[v]（子节点 v）
• 对于每个 u(≠1)，值 s[u] 表示**父边 (fa[u],u)**被多少条坏路径覆盖。

令坏路径条数为 cnt，若存在某个 u 使

• s[u] == cnt（父边被所有坏路径覆盖），且
• a[u] >= mx（父边权值足够被统一下调 mx），

则本次 x 是可行的。

这正是代码中 check(x) 的逻辑：统计坏路径、差分累加、枚举边看是否满足覆盖与承载的双条件。

三、为什么二分？边界如何取

我们要最小化“所有路径长度的最大值”，典型 二分答案：

• 上界 r = mx1：什么都不减，一定可行；
• 下界 l = mx1 - mx2：最佳情况下，把“极值路径”上某条边的最大权值 mx2 全减掉，最大路径也不可能低于 mx1 - mx2（再低就超出了能减的上限）。

在区间 [l, r] 上二分 mid，用 check(mid) 判可行性：

• 可行就尝试更小的 mid（右边界左移）；
• 不可行就增大 mid。

四、复杂度分析

• 预处理 DFS + 倍增 LCA：O(n log n)
• 每次 check(x)：差分清空 + 逐条路径处理 + 一次 DFS 汇总 + 线性扫边，O(n + m)
• 二分次数约 O(log(mx2)) / O(log(mx1)) 量级
  总复杂度：O((n log n) + (n+m) log W)，其中 W 为权值量级。

五、代码关键点对照

• dfs1：建树、记录 fa[][0] / dep / sum / a[v]；
• 倍增表：fa[i][j] = fa[fa[i][j-1]][j-1]；
• lca(x,y)：标准倍增 LCA；
• check(x)：
  • 统计坏路径 cnt 与所需统一减值上限 mx；
  • 差分 s[x]++，s[y]++，s[lca]-=2；
  • dfs2(1) 汇总；
  • 枚举所有父边 (fa[i], i)，判断 s[i]==cnt && a[i]>=mx；
• 二分答案并输出。

六、实现（与题给代码一致）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef __int128 i128;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=3e5+10;

int fa[N][22],dep[N],a[N],s[N],n,m;
struct P{int x,y,t;ll val;}b[N];
ll sum[N];
vector<pii> e[N];

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

void dfs1(int u)
{
    for(pii Edge:e[u])
    {
        int v=Edge.first,w=Edge.second;
        if(v!=fa[u][0])
        {
            fa[v][0]=u;
            a[v]=w;
            dep[v]=dep[u]+1;
            sum[v]=sum[u]+w;
            dfs1(v);
        }
    }
}

void dfs2(int u)
{
    for(pii Edge:e[u])
    {
        int v=Edge.first,w=Edge.second;
        if(v!=fa[u][0])
        {
            dfs2(v);
            s[u]+=s[v];
        }
    }
}

int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

bool check(ll x)
{
    memset(s,0,sizeof(s));
    ll mx=0,cnt=0;
    for(int i=1;i<=m;i++)
    {
        if(b[i].val>x)
        {
            cnt++;
            mx=max(mx,b[i].val-x);
            s[b[i].x]++,s[b[i].y]++;
            s[b[i].t]-=2;
        }
    }
    dfs2(1);
    for(int i=2;i<=n;i++) if(s[i]==cnt&&a[i]>=mx) return 1;
    return 0;
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        u=read(),v=read(),w=read();
        e[u].push_back(make_pair(v,w));
        e[v].push_back(make_pair(u,w));
    }
    dep[1]=1;
    dfs1(1);
    for(int j=1;j<=20;j++)
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    for(int i=1;i<=m;i++) b[i].x=read(),b[i].y=read();
    ll mx1=0,mx2=0;
    for(int i=1;i<=m;i++)
    {
        b[i].t=lca(b[i].x,b[i].y);
        mx1=max(mx1,b[i].val=sum[b[i].x]+sum[b[i].y]-sum[b[i].t]*2);
    }
    for(int i=2;i<=n;i++) mx2=max(mx2,1ll*a[i]);
    ll l=mx1-mx2,r=mx1,ans=-1;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout << ans << '\n';
    return 0;
}