• 原题链接。

挺好的一道题。

首先看到最小值最大，不难想到二分。但仔细思考，发现二分带给我们的便利是能清楚知道哪些边需要升级，可由于任意一个询问两点间边数都可以是 $O(n)$ 级别的，我们似乎很难直接维护。

于是我们接着想，既然每个询问所含边数过大，不便于一一遍历，那我们能不能将多个询问合在一起呢？这自然地引出了整体二分。

将边权离散化，我们将相同边权的边记在一起。每次整体二分时，边权小于等于 $mid$ 的边均需要升级，而我们此时需要快速维护的就是某个询问上需要升级的边的代价和。将代价记在每条边向下对应的点上。我们可以实时维护每个点到根节点的代价和，那么 $u,v$ 之间的代价就是

而对 $cost$ 地维护也是朴素的。具体地，每次点权修改都对应了一次子树内答案修改，于是树状数组维护 $dfn$ 序上区间加，单点查即可。

此时还有两个问题。第一是有些边可能升级了也不能满条件。我们可以预处理出两点间 $s$ 最大值，给二分加个上界即可。

第二则是整体二分时，我们需要将边权小于等于 $mid$ 的边标记，但我们不能全部枚举这些边，这样的话时间复杂度会假。于是可以考虑用不撤销整体二分的技巧，进入当前层时提前将边权在 $[1,l-1]$ 的边标记，当前层只处理 $[l,mid]$ 的边。具体可以看看 这道题。

时间复杂度 $O((n+q)\log^2n)$。

附核心代码：

inline void solve(int l,int r,int L,int R)
{
	if(l==r)
	{
		for(int i=L;i<=R;i++) ans[q[i].id]=vec[l];
		return void();
	}
	int mid=(l+r)>>1,p1=0,p2=0;
	for(int i=l;i<=mid;i++) for(auto x:d[i]) add(dfn[to[x]],w[x]),add(dfn[to[x]]+sz[to[x]],-w[x]);
	for(int i=L;i<=R;i++)
		if(q[i].mx<=vec[mid]||query(dfn[q[i].x])+query(dfn[q[i].y])-query(dfn[q[i].anc])*2>q[i].w) q1[++p1]=q[i];
		else q2[++p2]=q[i];
	for(int i=1;i<=p1;i++) q[L+i-1]=q1[i];
	for(int i=1;i<=p2;i++) q[L+p1+i-1]=q2[i];
	solve(mid+1,r,L+p1,R);
	for(int i=l;i<=mid;i++) for(auto x:d[i]) add(dfn[to[x]],-w[x]),add(dfn[to[x]]+sz[to[x]],w[x]);
	solve(l,mid,L,L+p1-1);
}

这道题还有二分加主席树的办法，这里就不赘述了。