P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance

思路：

注意到点对数量有 \(N^2\) 个，考虑丢掉一些无用的点对。

对于点对 \((x_1,y_1),(x_2,y_2)\)，满足 \(x_1 \le x_2 < y_2 \le y_1\)，即区间 \([x_2,y_2]\) 被 \([x_1,y_1]\) 包含，此时满足若询问到了 \([x_1,y_1]\)，则一定会询问到 \([x_2,y_2]\)。

若满足 \(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\)，那么此时可以将 \((x_1,y_1)\) 舍弃，因为若要用 \((x_1,y_1\)) 的贡献，不如直接去看 \((x_2,y_2)\) 的贡献，毕竟 \((x_1,y_1)\) 的贡献一定不会比 \((x_2,y_2)\) 更优。

那么我们可以定义若两个点对 \((x_1,y_1),(x_2,y_2)\) 满足以下条件，则称 \((x_1,y_1)\) 被 \((x_2,y_2)\) 支配：

• \(x_1 \le x_2 < y_2 \le y_1\)。

• \(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\)。

此时定义一个支配点对满足没有被任何一个点对支配，即我们需要找出所有的支配点对来计算贡献。

注意到是一个树上点对距离问题，考虑点分治解决。

令当前分治重心为 \(rt\)，对于点 \(v\)，令 \(S_v\) 表示当前联通块中所有满足 \(\operatorname{dis}(i,rt) \le \operatorname{dis}(v,rt)\) 的 \(i\) 组成的一个集合。

那么可以与 \(v\) 组成支配点对的点一定是 \(S_v\) 中 \(v\) 的前驱和后继，即 \(S_v\) 中 \(<v\) 中最大的数和 \(>v\) 中最小的数。

简单证一下，设 \(S_v\) 中 \(v\) 的前驱为 \(u\)：

• 有 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,rt) + \operatorname{dis}(u,rt) \le \operatorname{dis}(i,rt) + \operatorname{dis}(v,rt) = \operatorname{dis}(i,v)\)，即 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,v)\)。

• 注意到此时 \(i < u < v\) 或 \(u < v < i\)，即 \((i,v)\) 被 \((i,u)\) 支配或 \((u,i)\) 被 \((v,i)\) 支配。

• 那么只有当 \(i=u\) 时，\((u,u)\) 点对不存在，\((u,v)\) 不会被其它 \(S_v\) 中的点对支配。

后继情况类似，就不多说了。

然后考虑如何快速找到支配点对，直接按照上面的方法找 \(S_v\)，复杂度肯定是 \(O(N^2)\) 起步，考虑优化。

首先对于整个联通块的所有点，按照点的编号排序升序，然后维护一个 \(\operatorname{dis}(i,rt)\) 不降的单调栈。

那么有一个性质是，对于被点 \(i\) 弹出去的点 \(u\)，肯定满足 \(i\) 是 \(u\) 后面第一个小于等于 \(\operatorname{dis}(u,rt)\) 的点且编号最小，即 \(i\) 是 \(S_u\) 中 \(u\) 的前驱；然后再倒着降序做一遍单调栈找后继即可。

此时我们来估算一下支配点对的数量，每个点最多被 \(\log N\) 个分治重心包含，每次包含最多增加 \(2\) 对支配点对，即总支配点对的数量为 \(N \log N\) 左右。

现在求出了全部的支配点对，即有贡献的点对，现在考虑如何求被一个区间包含的所有支配点对的最小贡献值，可以在线使用树套树，但是没必要。

考虑离线使用扫描线算法，因为树状数组不好维护后缀最值，考虑倒着扫左端点，然后对于每个点对，在左端点处将右端点贡献加入进去；那么对于一个在左端点的询问，就是一个前缀最小值。

时间复杂度为 \(O(N \log^2 N + Q \log N)\)。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2e5+10,M=1e6+10,INF=1e18; 
bool Begin;
inline ll read(){
    ll 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<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
int n,q;
ll ans[M];
vector<int> G[N];
vector<pair<int,ll>> E[N],Q[N];
void add(int u,int v,int w){
	E[u].push_back({v,w});
	E[v].push_back({u,w});
}
namespace Lowbit{
	ll a[N];
	inline void init(){
		for(int i=1;i<=n;i++)
		  a[i]=INF;
	}
	inline void add(int x,ll w){
		for(int i=x;i<=n;i+=lowbit(i))
		  a[i]=min(a[i],w);
	}
	inline ll query(int x){
		ll ans=INF;
		for(int i=x;i;i-=lowbit(i))
		  ans=min(ans,a[i]);
		return ans;
	}	
};
namespace LCA{
	int p[N],t[N],z[N],d[N],fa[N];
	ll dep[N];
	inline void dfs1(int u,int f){
		p[u]=1;
		for(auto t:E[u]){
			int v=t.first,w=t.second;
			if(v==f)
			  continue;
			dep[v]=dep[u]+w;
			d[v]=d[u]+1;
			fa[v]=u;
			dfs1(v,u);
			p[u]+=p[v];
			if(p[v]>p[z[u]])
			  z[u]=v;
		}
	}
	inline void dfs2(int u,int k){
		t[u]=k;
		if(!z[u])
		  return ;
		dfs2(z[u],k);
		for(auto t:E[u]){
			int v=t.first;
			if(v==fa[u]||v==z[u])
			  continue;
			dfs2(v,v);
		}
	}
	inline int Lca(int u,int v){
		while(t[u]!=t[v]){
			if(d[t[u]]<d[t[v]])
			  swap(u,v);
			u=fa[t[u]];
		}
		return d[u]<d[v]?u:v;
	}
	inline ll dis(int u,int v){
		return dep[u]+dep[v]-(dep[Lca(u,v)]<<1ll);
	}
	inline void init(){
		dfs1(1,1);
		dfs2(1,1);
	}
};
namespace Tree{
	int sum,cnt,top,Max,root;
	int T[N],siz[N];
	pair<int,ll> dis[N];
	bool del[N];
	inline void add(int x,int y){
		if(x>y)
		  swap(x,y);
		G[x].push_back(y);
	}
	inline void getroot(int u,int fa){
		int s=0;
		siz[u]=1;
		for(auto t:E[u]){
			ll v=t.first;
			if(del[v]||v==fa)
			  continue;
			getroot(v,u);
			siz[u]+=siz[v];
			s=max(s,siz[v]);
		}
		s=max(s,sum-siz[u]);
		if(s<Max){
			Max=s;
			root=u;
		}
	}
	inline void Get(int u,int p){
		root=0;
		sum=Max=p;
		getroot(u,0);
		getroot(root,0);
	}
	inline void getdis(int u,int fa,ll d){
		dis[++cnt]={u,d};
		for(auto t:E[u]){
			int v=t.first,w=t.second;
			if(v==fa||del[v])
			  continue;
			getdis(v,u,d+w);
		}
	}
	inline void calc(int u){
		cnt=0;
		getdis(u,0,0);
		sort(dis+1,dis+cnt+1);
		top=0;
		for(int i=1;i<=cnt;i++){
			while(top&&dis[i].second<=dis[T[top]].second){
				add(dis[i].first,dis[T[top]].first);
				top--;
			}
			T[++top]=i;
		}
		top=0;
		for(int i=cnt;i>=1;i--){
			while(top&&dis[i].second<=dis[T[top]].second){
				add(dis[i].first,dis[T[top]].first);
				top--;
			}
			T[++top]=i;			
		}
	}
	inline void solve(int u){
		calc(u);
		del[u]=1;
		for(auto t:E[u]){
			int v=t.first;
			if(del[v])
			  continue;
			Get(v,siz[v]);
			solve(root);
		}
	}	
	void work(){
		Lowbit::init();
		LCA::init();
		Get(1,n);
		solve(root);
	}
};
bool End;
int main(){
//	open("A.in","A.out");
	n=read();
	for(int u,v,w,i=1;i<n;i++){
		u=read(),v=read(),w=read();
		add(u,v,w); 
	}
	q=read();
	for(int l,r,i=1;i<=q;i++){
		l=read(),r=read();
		Q[l].push_back({i,r});
	}
	Tree::work();
	for(int i=n;i>=1;i--){
		for(auto v:G[i])
		  Lowbit::add(v,LCA::dis(i,v));
		for(auto t:Q[i])
		  ans[t.first]=Lowbit::query(t.second);
	}
	for(int i=1;i<=q;i++){
		write(ans[i]==INF?-1:ans[i]);
		putchar('\n');
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

热门相关：战斗就变强   我能看到隐藏机缘   风流医圣   闪婚总裁很惧内   大金主，你别假正经了