借鉴第一篇题解,代码如下

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+c-48;c=getchar();}return x*f;}
const int maxn = 3e5 + 5;

int x[maxn],y[maxn],z[maxn],p[maxn];//u,v,w,点的权值
int dson[maxn],siz[maxn],dep[maxn],f[maxn],rt;//重儿子，大小，深度，父亲
int id[maxn],top[maxn],rk[maxn],num;//树剖
int C[maxn],d[maxn],st[maxn];
int maxa,maxb,maxc,n,m;


//---------------------------------------------------


struct BIT
{
    int c[maxn];
    int lowbit(int x)
    {
        return x & (-x);
    }
    void update(int x,int k)
    {
        for(int i = x;i <= n;i += lowbit(i))
        {
            c[i] += k;
        }
    }
    int query(int x)
    {
        int ans = 0;
        for(int i = x;i >= 1;i -= lowbit(i))
        {
            ans += c[i];
        }
        return ans;
    }
    void init()
    {
        for(int i = 1;i <= n;i++)
        {
            update(i,p[rk[i]]);
        }
    }
    int sum(int l,int r)
    {
        return query(r) - query(l - 1);
    }
}B;//树状数组


//------------------------------------------------------


int max(int x,int y)
{
    if(x > y)return x;
    return y;
}

struct Seg
{
    #define ls p << 1
    #define rs p << 1 | 1
    int zlt[maxn << 2],tag[maxn << 2];
    void pushdown(int p)
    {
        if(!tag[p])
        {
            return ;
        }
        zlt[ls] = max(zlt[ls],tag[p]);
        zlt[rs] = max(zlt[rs],tag[p]);
        tag[ls] = max(tag[ls],tag[p]);
        tag[rs] = max(tag[rs],tag[p]);
        tag[p] = 0;
        return ;
    }
    void pushup(int p)
    {
        zlt[p] = max(zlt[ls],zlt[rs]);
    }
    void Update(int p,int L,int R,int l,int r,int v)//更新
    {
        if(L > r || R < l)
        {
            return ;
        }
        if(l <= L && R <= r)
        {
            zlt[p] = max(zlt[p],v);
            tag[p] = max(tag[p],v);
            return ;
        }
        pushdown(p);
        int mid = L + R >> 1;
        Update(ls,L,mid,l,r,v);
        Update(rs,mid + 1,R,l,r,v);
        pushup(p);
    }
    int Query(int x,int y,int p,int k)
	{
		if(x == y)
        {
            return zlt[p];
        }
		pushdown(p);
        int mid = x + y >> 1;
		if (k <= mid)
        {
            return Query(x,mid,ls,k);
        }
		else
        {
            return Query(mid + 1,y,rs,k);
        }
	}
}SEG;


//------------------------------------------------------


struct edge
{
    int nxt,to;
}e[maxn << 1];
int head[maxn],tot;

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

//树剖-------------------------------------------------

inline void dfs(int u,int fa)//树剖
{
	f[u] = fa;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
	for(int i = head[u];i;i = e[i].nxt)
	{
        int v = e[i].to;
		if (v == fa)
        {
            continue;
        }
		dfs(v,u);
		siz[u] += siz[v];
		if (siz[v] > siz[dson[u]])
        {
            dson[u] = v;
        }
	}
	return;
}

inline void dfs2(int u,int fa)
{
    top[u] = fa;
    id[u] = ++num;
    rk[id[u]] = u;
	if (!dson[u])
    {
        return;
    }
	dfs2(dson[u],fa);
	for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
		if(v != f[u] && v != dson[u])
        {
            dfs2(v,v);
        }
    }
	return;
}//树剖

//计算答案---------------------------------------------

inline int Sum(int u,int v)
{
    int tu = top[u],tv = top[v],ans = 0;
    while(tu != tv)
	{
		if(dep[tu] >= dep[tv])
        {
            ans += B.sum(id[tu],id[u]);
            u = f[tu];
            tu = top[u];
        }
        else
        {
            ans += B.sum(id[tv],id[v]);
            v = f[tv];
            tv = top[v];
        }
	}
    if(id[u] <= id[v])	ans += B.sum(id[u] + 1,id[v]);
	else ans += B.sum(id[v] + 1,id[u]);
    return ans;
}

inline bool cmp(int x,int y)
{
    return C[x] < C[y];
}

inline void up(int u,int v,int w)
{
    int tu = top[u],tv = top[v],t = 0;
    while(tu != tv)
	{
		if(dep[tu] >= dep[tv])
        {
            C[++t] = id[tu];
            d[t] = id[u];
            u = f[tu];
            tu = top[u];
        }
        else
        {
            C[++t] = id[tv];
            d[t] = id[v];
            v = f[v];
            tv = top[v];
        }
	}
    if(id[u] <= id[v])
    {
        C[++t] = id[u] + 1;
        d[t] = id[v];
    }
    else
    {
        C[++t] = id[v] + 1;
        d[t] = id[u];
    }
    for(int i(1);i <= t;++i)
    {
        st[i] = i;
    }
    sort(st + 1,st + t + 1,cmp);
    if(C[st[1]] > 1)
    {
        SEG.Update(1,1,n,1,C[st[1]] - 1,w);
    }
    if(d[st[t]] < n)
    {
        SEG.Update(1,1,n,d[st[t]] + 1,n,w);
    }
    for(int i(1);i < t;++i)
    {
        SEG.Update(1,1,n,d[st[i]] + 1,C[st[i + 1]] - 1,w);
    }
}
inline int Find(int u,int v)
{
    int ans = 0x3f3f3f3f;
    if(u == v)
    {
        return 0;
    }
    if(dep[u] < dep[v])
    {
        swap(u,v);
    }
    while(dep[u] != dep[v])
    {
        ans = min(ans,max(maxc - p[u],SEG.Query(1,n,1,id[u])));
        u = f[u];
    }
	while(u != v)
	{
		if(dep[u] > dep[v])
        {
            ans = min(ans,max(maxc - p[u],SEG.Query(1,n,1,id[u])));
            u = f[u];
        }
        else
        {
            ans = min(ans,max(maxc - p[v],SEG.Query(1,n,1,id[v])));
            v = f[v];
        }
	}
	return ans;
}

//-----------------------------------------------

int main()
{
    n = read();
    m = read();
    for(int i(1);i < n;++i)
    {
        x[i] = read();
        y[i] = read();
        z[i] = read();
    }
    for(int i(1);i < n;++i)
    {
        add_edge(x[i],y[i]);
        add_edge(y[i],x[i]);
    }
    rt = 1;
    dfs(rt,0);
    dfs2(rt,rt);//树剖
    for(int i(1);i < n;++i)
    {
        if(dep[x[i]] > dep[y[i]])
        {
            p[x[i]] = z[i];
        }
        else
        {
            p[y[i]] = z[i];
        }
    }
    B.init();
    for(int i(1);i <= m;++i)
    {
        int a,b,tmp;
        a = read();
        b = read();
        tmp = Sum(a,b);
        up(a,b,tmp);
        if(tmp >= maxc)
        {
            maxa = a;
            maxb = b;
            maxc = tmp;
        }
    }
    printf("%d",Find(maxa,maxb));
    return 0;
}