WA+MLE求条，新思路(线段树+树刨+暴力做法)

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,c,dfn[300010],dfw[300010],dep[300010],top[300010];
int bson[300010],cnt,e[1000010],ne[1000010],h[300010],w[300010],idx;
int lzy[1200010],siz[300010],fa[300010],dis[300010];
struct tree
{
    int l,r,maxn,cnt;
}tr[1200010];
struct sad
{
    int s,t,dis;
    bool operator<(const sad &a) const
    {
        return dis > a.dis;
    }
}ed[300010];
void add(int a,int b,int c)
{
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}
tree comp(tree a,tree b)
{
    if (a.cnt > b.cnt) return a;
    else if (a.cnt < b.cnt) return b;
    else
    {
        tree tmp; tmp.cnt = a.cnt;
        tmp.maxn = max(a.maxn,b.maxn);
        return tmp;
    }
}
void pushup(int u)
{
    
    tree tmp = comp(tr[u<<1],tr[u<<1|1]);
    tr[u].cnt = tmp.cnt; tr[u].maxn = tmp.maxn;
}
void pushdown(int u)
{
    lzy[u<<1] += lzy[u]; lzy[u<<1|1] += lzy[u];
    tr[u<<1].cnt += lzy[u]; tr[u<<1|1].cnt += lzy[u];
    lzy[u] = 0;
}
void build(int u,int l,int r)
{
    if (l == r) tr[u] = {l,l,dfw[l],0};
    else
    {
        int mid = (l+r)>>1;
        tr[u] = {l,r,0,0};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
tree query(int u,int l,int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else if (!(tr[u].l > r || tr[u].r < l))
    {
        pushdown(u);
        tree a = query(u<<1,l,r);
        tree b = query(u<<1|1,l,r);
        return comp(a,b);
    }
    tree tmp = {0,0,0,0};
    return tmp;
}
void modify(int u,int l,int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt++;
        lzy[u]++;
    }
    else if (!(tr[u].l > r || tr[u].r < l))
    {
        pushdown(u);
        modify(u<<1,l,r);
        modify(u<<1|1,l,r);
        pushup(u);
    }
}
void dfs1(int x,int f)
{
    dep[x] = dep[f]+1; siz[x] = 1;
    fa[x] = f;
    int maxn = -1;
    for (int i = h[x];~i;i = ne[i])
    {
        int j = e[i];
        if (j == f) continue;
        dis[j] = dis[x]+w[i];
        dfs1(j,x);
        siz[x] += siz[j];
        if (siz[j] > maxn)
        {
            maxn = siz[j];
            bson[x] = j;
        }
    }
}
void dfs2(int x,int t)
{
    dfn[x] = ++cnt; top[x] = t;
    int tmp = cnt;
    if (!bson[x]) return;
    dfs2(bson[x],t);
    for (int i = h[x];~i;i = ne[i])
    {
        int j = e[i];
        if (j == fa[x])
        {
            dfw[tmp] = w[i];
            continue;
        }
        if (j == bson[x]) continue;
        dfs2(j,j);
    }
}
int lca(int x,int y)
{
    while(top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x,y);
    return x;
}
int dist(int x,int y)
{
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
void pathmod(int x,int y)
{
    while(top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        modify(1,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x,y);
    modify(1,dfn[x]+1,dfn[y]);
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    for (int i = 1;i < n;i++)
    {
        cin >> a >> b >> c;
        add(a,b,c); add(b,a,c);
    }
    dfs1(1,0); dfs2(1,1);
    build(1,1,n);
    for (int i = 0;i < m;i++)
    {
        cin >> ed[i].s >> ed[i].t;
        ed[i].dis = dist(ed[i].s,ed[i].t);
    }
    sort(ed,ed+m);
    ed[m].dis = -1;
    int la = ed[0].dis;
    int num = 0,ans = 0,maxn = la;
    for (int i = 0;i <= m;i++)
    {
        if (ed[i].dis == la)
        {
            pathmod(ed[i].s,ed[i].t);
            num++;
        }
        else
        {
            if (tr[1].cnt != num)
            {
                ans = max(ans,la);
                break;
            }
            else
            {
                ans = max(ans,maxn-tr[1].maxn);
            }
            la = ed[i].dis;
            if (la < ans) break;
            pathmod(ed[i].s,ed[i].t);
            num++;
        }
    }
    cout << ans;
    return 0;
}