讲解 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)\)。

完整代码：

<code>#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;

}