自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:44:59，当前版本为作者最后更新于2023-02-11 13:57:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

这题之前在 Ynoi 以强制在线、不带边权和 $5\times 10^4$ 的数据范围作为一个 $O(n\sqrt n)$ 题目出现过，这个是解法，后来被替换掉了。

现在它变成了 polylog 的题再次进入 Ynoi。

$\text{Upd2023.3.7}$：修正一个小错误，感谢

$\text{Upd2023.11.1}$：修正一处 $\min$ 写成 $\max$。

题意

给出一颗 $n$ 个点的有权树，$q$ 次询问，每次询问给出 $l,r$，求 $\displaystyle\min_{l\le i<j\le r}\text{dis}(i,j)$。允许离线。

$n\le 2\times 10^5$，$q\le 10^6$。

思路

最近点对问题有一个通用思路，就是找“支配点对”，也就是说，有许多的点对是没有用的。

由于树上距离涉及路径，我们可以思考点分治。对于一次分治，我们要思考这个连通块两两之间有哪些是会计入最终有效点对的。

考虑将连通块内所有点 $p$ 以二元组 $(p,a_p)$ 表示，其中 $a_p$ 表示 $\text{dis}(p,r)$，$r$ 为当前分治中心。则对于点对 $(p,q)$，我们有 $\text{dis}(p,q)\le a_p+a_q$。（为什么是 $\le$ 号？因为 $p,q$ 可能来自分治中心的同一个子树。但是这种情况我们无需特殊处理，默认 $\text{dis}(p,q)=a_p+a_q$，原因下文将给出）

我们考虑一下这层分治的有效点对 $(i,k)$，无效点对 $(i,j),(j,k)$，其中 $i<j<k$。对 $i$ 考虑 $(i,k)$ 有效相当于 $\text{dis}(i,j)>\text{dis}(i,k)$ 即 $a_j>a_k$，对 $k$ 有类似的 $a_j>a_i$，即 $a_i<a_j,a_k<a_j$。所以对于有效点对 $(l,r)$，$\max(a_l,a_r)<\displaystyle\min_{i=l+1}^{r-1}a_i$。

有一个想法是，按 $a_p$ 的值从小到大排序，初始时有一空集，依次向集合中加入对应的 $p$。设加入 $p$ 之前，集合里 $p$ 的前驱为 $v$、后继为 $w$，则 $(p,v)$ 和 $(p,w)$ 都是有效点对。容易用 set 维护。每个点在每个包含它的分治只会加入 $O(1)$ 组合法点对，则总合法点对数是 $O(n\log n)$ 的。

说一下不用管同子树的点对的影响的原因：同子树内的点对的距离只会更近，把距离放大了还比不过那就说明被淘汰掉的点对是无效的了。

考虑找出所有的合法点对 $(i,j),i<j$ 后怎么做，用扫描线，维护序列 $t$，扫到 $j$ 的时候 $t_i=\min(t_i,\text{dis}(i,j))$，扫到 $r$ 处理 $[l,r]$ 询问，即查询 $\displaystyle\min_{p=l}^r t_p$ 等价于单点取 $\min$ 后缀 $\min$，用树状数组即可搞定。

点分治部分每一层是 $O(s\log s)$ 的，总共是 $O(n\log^2n)$，扫描线有 $O(n\log n)$ 组修改和 $q$ 组查询，复杂度为 $O(n\log^2n+q\log n)$，总时间复杂度 $O(n\log ^2n+q\log n)$，空间复杂度 $O(n\log n+q)$。

但是这么写你会被卡常。

考虑优化找有效点对的过程，我们发现这个过程等价于按 $p$ 排序，维护 $a_p$ 的单调不减的单调栈，按 $p$ 顺序加入 $a_p$，在弹出栈顶所有大于 $a_p$ 的数后，设栈顶为 $a_v$，则 $(v,p)$ 为一对有效点对。我们正反做两遍即可。

时空复杂度不变。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define mpr make_pair
#define fir first
#define sec second
const int N=2e5+10,M=1e6+10,INF=1e9;
const ll INF_=1e18;
int n,q,head[N],cnt,siz[N],top;
bool del[N];
ll ans[M];
pil stk[N],stk2[N];
int top2;
vector<int>use[N];
struct Edge{
	int to,nxt,w;
}a[N<<1];
struct Query{
	int l,id;
};
vector<Query>qr[N];
inline void add(int u,int v,int w){
	cnt++;
	a[cnt].to=v;
	a[cnt].nxt=head[u];
	a[cnt].w=w;
	head[u]=cnt;
}
inline void push(int u,int v){
	if(u>v) swap(u,v);
	use[v].emplace_back(u);
}
inline pii findroot(int rt,int f,int pre){
	siz[rt]=1;
	int mx=0;
	pii ans=make_pair(INF,0);
	for(int i=head[rt];i;i=a[i].nxt){
		int t=a[i].to;
		if(del[t]||t==f) continue;
		ans=min(ans,findroot(t,rt,pre));
		siz[rt]+=siz[t];
		mx=max(mx,siz[t]);
	}
	ans=min(ans,mpr(max(mx,pre-siz[rt]),rt));
	return ans;
}
inline void dfs(int rt,int f,ll s){
	stk[++top]=mpr(rt,s);
	for(int i=head[rt];i;i=a[i].nxt){
		int t=a[i].to;
		if(t==f||del[t]) continue;
		dfs(t,rt,s+a[i].w);
	}
}
inline void solve(int rt,int pre){
	int root=findroot(rt,0,pre).second;
	int res=siz[rt];
	del[root]=1;
	top=0;
	for(int i=head[root];i;i=a[i].nxt){
		int t=a[i].to;
		if(del[t]) continue;
		dfs(t,root,a[i].w);
	}
	stk[++top]=mpr(root,0);
	sort(stk+1,stk+top+1);
	top2=0;
	for(int i=1;i<=top;i++){
		int id=stk[i].fir;
		ll d=stk[i].sec;
		while(top2&&stk2[top2].sec>d) top2--;
		push(id,stk2[top2].fir);
		stk2[++top2]=stk[i];
	}
	top2=0;
	for(int i=top;i>=1;i--){
		int id=stk[i].fir;
		ll d=stk[i].sec;
		while(top2&&stk2[top2].sec>d) top2--;
		push(id,stk2[top2].fir);
		stk2[++top2]=stk[i];
	}
	for(int i=head[root];i;i=a[i].nxt){
		int t=a[i].to;
		if(del[t]) continue;
		solve(t,res);
	}
}
struct ST_table{
	int dep[N],ind[N],lg[N<<1],cnt,st[20][N<<1];
	ll de[N];
    inline void dfs(int rt,int f){
        dep[rt]=dep[f]+1;
        st[0][++cnt]=rt,ind[rt]=cnt;
        for(int i=head[rt];i;i=a[i].nxt){
            int t=a[i].to;
            if(t==f) continue;
            de[t]=de[rt]+a[i].w;
            dfs(t,rt);
            st[0][++cnt]=rt;
        }
    }
    inline int cmp(int x,int y){
        return dep[x]<dep[y]?x:y;
    }
    inline void init(){
        dfs(1,0);
        for(int i=1;(1<<i)<=cnt;i++)
            for(int j=1;j+(1<<i)-1<=cnt;j++)
                st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<i-1)]);
        for(int i=2;i<=cnt;i++)
            lg[i]=lg[i>>1]+1;
    }
    inline int LCA(int x,int y){
        x=ind[x],y=ind[y];
        if(x>y) swap(x,y);
        int i=lg[y-x+1];
        int p=1<<i;
        return cmp(st[i][x],st[i][y-p+1]);
    }
    inline ll dis(int x,int y){
        return de[x]+de[y]-2*de[LCA(x,y)];
    }
}s;
struct BIT{
	#define lowbit(i) (i&-i)
	ll t[N];
	inline void init(){
		for(int i=1;i<=n;i++)
			t[i]=INF_;
	}
	inline void add(int p,ll v){
		for(int i=p;i;i-=lowbit(i))
			t[i]=min(t[i],v);
	}
	inline ll query(int p){
		ll ans=INF_;
		for(int i=p;i<=n;i+=lowbit(i))
			ans=min(ans,t[i]);
		return ans;
	}
}T;
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	solve(1,n);
	s.init();
	T.init();
	q=read();
	for(int i=1;i<=q;i++){
		int l=read(),r=read();
		if(l>=r) ans[i]=-1;
		else qr[r].emplace_back((Query){l,i});
	}
	for(int i=1;i<=n;i++){
		sort(use[i].begin(),use[i].end());
		use[i].resize(unique(use[i].begin(),use[i].end())-use[i].begin());
	}
	for(int i=1;i<=n;i++){
		for(auto t:use[i])
			T.add(t,s.dis(t,i));
		for(auto t:qr[i])
			ans[t.id]=T.query(t.l);
	}
	for(int i=1;i<=q;i++)
		write(ans[i]),putc('\n');
	flush();
}