支配对
yangzichen1203
·
·
算法·理论
参考资料：https://www.luogu.com.cn/article/rmdqa1b8
1
P5926 [JSOI2009] 面试的考验
CF765F Souvenirs
CF1793F Rebrending
$$\min_{l\le i<j\le r}|a_i-a_j|$$
:::success[Solution]
对每个点考虑 $i$ 考虑 $i<j,a_i\le a_j$ 的点对 $(i,j)$。
$i<j,a_i\ge a_j$ 同理。
考虑这些点对之间的支配关系。
若 $(i,j)$ 是支配对，$i<j<k$，$(i,k)$ 是支配对一定需要
$$a_k-a_i<a_j-a_i,a_k-a_i<a_j-a_k$$
$$a_k<a_j,a_k<\dfrac{a_i+a_j}{2}$$
$$a_k<\dfrac{a_i+a_j}{2}$$
我们不要求枚举所有真正不可被任意点对支配的点对，只需要枚举一个充分不必要的候选集。
对于 $i$ 每次向右找第一个符合条件的 $j$，然后更新条件，最多找 $O(\log V)$ 次。
使用动态开点权值线段树维护每个权值所在位置，记录最小位置，从右到左扫时动态插入即可单次操作 $O(\log n)$。
一共最多存在 $O(n\log V)$ 个支配对，将询问离线，通过扫描线解决一维，树状数组维护另一维。
时间复杂度：$O(n\log V\log n+m\log n)$。
空间复杂度：$O(n\log V)$。
:::
:::success[Code]
由于是很久前写的，与题解思路相同，细节上左右方向相反。
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 100005
#define V 1000000000
#define inf (1<<30)
int n,m,a[MAXN];
struct Node{
int ls,rs,max;
}tr[MAXN*32];
int cnt=0,rt=0;
inline int newnode(){
tr[++cnt]={0,0,0};
return cnt;
}
void insert(int &c,int L,int R,int x,int k){
if(!c) c=newnode();
tr[c].max=max(tr[c].max,k);
if(L==R) return ;
int mid=(L+R)>>1;
if(x<=mid) insert(tr[c].ls,L,mid,x,k);
else insert(tr[c].rs,mid+1,R,x,k);
}
int query(int c,int L,int R,int l,int r){
if(!c||l>r) return 0;
if(l<=L&&r>=R) return tr[c].max;
int mid=(L+R)>>1;
int ans=0;
if(l<=mid) ans=max(ans,query(tr[c].ls,L,mid,l,r));
if(r>mid) ans=max(ans,query(tr[c].rs,mid+1,R,l,r));
return ans;
}
int b[MAXN];
void add(int x,int k){
while(x){
b[x]=min(b[x],k);
x-=x&-x;
}
}
int query(int x){
int ans=inf;
while(x<=n){
ans=min(ans,b[x]);
x+=x&-x;
}
return ans;
}
struct Que{
int l,r,id;
}q[MAXN];
int ans[MAXN];
void solve(){
For(i,1,n){
b[i]=inf;
}
cnt=0;rt=0;
int now=1;
For(i,1,n){
int l=1,r=a[i]-1;
while(1){
int x=query(rt,1,V,l,r);
if(x==0) break;
add(x,a[i]-a[x]);
l=(a[i]+a[x])/2+1;
}
insert(rt,1,V,a[i],i);
while(now<=m&&q[now].r==i){
ans[q[now].id]=min(ans[q[now].id],query(q[now].l));
now++;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
For(i,1,n){
cin>>a[i];
}
For(i,1,m){
cin>>q[i].l>>q[i].r;
q[i].id=i;
ans[i]=inf;
}
sort(q+1,q+m+1,[&](Que x,Que y){
return x.r<y.r;
});
solve();
For(i,1,n){
a[i]=V+1-a[i];
}
solve();
For(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
:::
# 2
[P7880 [Ynoi2006] rldcot](https://www.luogu.com.cn/problem/P7880)：
$n$ 个点的树，点带权，$m$ 次询问 $[l,r]$，求
$$|\{a_{LCA(x,y)}|l\le x\le y\le r\}|$$
:::success[Solution]
抽象为二维平面矩形数颜色，则时间复杂度与点数强相关。
总共有 $O(n^2)$ 个点，考虑减小有效点数量。
如果 $l_1\le l_2\le r_2\le r_1,LCA(l_1,r_1)=LCA(l_2,r_2)$，则称 $(l_2,r_2)$ 支配了 $(l_1,r_1)$，我们只保留 $(l_2,r_2)$ 即可。
考虑用 dsu on tree 找出这些支配对。
对于当前递归，对每棵子树 $u$ 考虑其左侧子树的点集，则只有其集合内前驱 $v$ 后继 $w$ 会产生支配对 $(v,u),(u,w)$。
需要注意的是对于整棵子树，先查找前驱后继再插入点。
支配对数 $O(n\log n)$，用平衡树维护集合，时间复杂度 $O(n\log^2 n)$。
二维平面矩形数颜色就直接对询问离线下来，按 $r$ 排序，只记录每种颜色最后出现的位置，树状数组统计贡献即可。
时间复杂度：$O(n\log^2 n+m\log n)$。
空间复杂度：$O(n\log n+m)$。
:::
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 100005
#define MAXM 500005
int n,m;
vector<pair<int,int>> e[MAXN];
long long a[MAXN];
int fa[MAXN],sz[MAXN],son[MAXN];
void dfs1(int u,int f){
fa[u]=f;
sz[u]=1;
int Max=0;
for(auto [v,d]:e[u]){
if(v==f) continue;
a[v]=a[u]+d;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>Max){
Max=sz[v];
son[u]=v;
}
}
}
int dfn[MAXN],pos[MAXN],tot=0,top[MAXN];
void dfs2(int u,int t){
dfn[u]=++tot;
pos[tot]=u;
top[u]=t;
if(!son[u]) return ;
dfs2(son[u],t);
for(auto [v,d]:e[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int V;
struct Que{
int l,op,id;
};
vector<Que> q[MAXN];
void init(){
dfs1(1,0);
dfs2(1,1);
vector<long long> v;
For(i,1,n){
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
V=v.size();
For(i,1,n){
a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
}
set<int> s;
auto calc=[&](int x,int a){
auto it=s.lower_bound(x);
if(it!=s.begin()){
q[x].push_back({*prev(it),0,a});
}
it=s.upper_bound(x);
if(it!=s.end()){
q[*it].push_back({x,0,a});
}
};
dFor(i,n,1){
int u=pos[i];
for(auto [v,d]:e[u]){
if(v==fa[u]||v==son[u]) continue;
For(j,dfn[v],dfn[v]+sz[v]-1){
calc(pos[j],a[u]);
}
For(j,dfn[v],dfn[v]+sz[v]-1){
s.insert(pos[j]);
}
}
s.insert(u);
q[u].push_back({u,0,(int)a[u]});
if(u==top[u]){
For(i,dfn[u],dfn[u]+sz[u]-1){
s.erase(s.find(pos[i]));
}
}
}
}
int tr[MAXN];
void add(int x,int k){
while(x){
tr[x]+=k;
x-=x&-x;
}
}
int query(int x){
int ans=0;
while(x<=n){
ans+=tr[x];
x+=x&-x;
}
return ans;
}
int lst[MAXN],ans[MAXM];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
For(i,1,n-1){
int u,v,d;
cin>>u>>v>>d;
e[u].push_back({v,d});
e[v].push_back({u,d});
}
init();
For(i,1,m){
int l,r;
cin>>l>>r;
q[r].push_back({l,1,i});
}
For(r,1,n){
for(auto [l,op,id]:q[r]){
if(op==0){
if(l>lst[id]){
if(lst[id]){
add(lst[id],-1);
}
add(l,1);
lst[id]=l;
}
}else{
ans[id]=query(l);
}
}
}
For(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
:::
# 3
[P8528 [Ynoi2003] 铃原露露](https://www.luogu.com.cn/problem/P8528)：
$n$ 个点的树，$m$ 次询问 $[l,r]$，求
$$|\{(L,R)|l\le L\le R\le r,\forall L\le a_x,a_y\le R,L\le a_{LCA(x,y)}\le R\}|$$
:::success[Solution]
合法交等价于非法并。
令 $a_u<a_v$，对于点对 $(u,v)$，设 $w=LCA(u,v)$，考虑其对查询区间的贡献。
若 $a_w\in [1,a_u-1]$，则使得 $L\in [a_w+1,a_u],R\in [a_v,n]$ 非法。
若 $a_w\in [a_u,a_v]$，则无贡献。
若 $a_w\in [a_v+1,n]$，则使得 $L\in [1,a_u],R\in [a_v,a_w-1]$ 非法。
考虑支配对关系，若 $L_{(u_1,v_1)}\subseteq L_{(u_2,v_2)},R_{(u_1,v_1)}\subseteq R_{(u_2,v_2)}$，则 $(u_1,v_1)$ 被 $(u_2,v_2)$ 支配。
看到 LCA，考虑使用 dsu on tree 找到所有支配对。
对于当前递归，根为 $w$，设当前枚举点 $u$。
假设 $a_u<a_v$，$a_u>a_v$ 同理。
若 $a_u<a_w$，取 $a_u$ 的后继 $a_v$，若 $a_v<a_w$，则存在支配对 $(u,v)$，否则不存在此类支配对。
若 $a_u>a_w$，取 $a_u$ 的后继 $a_v$，则存在支配对 $(u,v)$。
同样需要注意对整棵子树先查询支配对再加入点。
支配对数 $O(n\log n)$，用平衡树维护集合，时间复杂度 $O(n\log^2 n)$。
查询就等价于对二维平面矩形覆盖，矩形求和，对一维差分后扫描线，另一维用线段树维护即可。
线段树维护区间最小值，区间最小值出现次数，区间加标记，区间历史合法次数，区间时间差。
注意修改矩形是一定全部满足 $l\le r$，查询矩形一半不满足 $l\le r$，做完后直接减掉即可。
时间复杂度：$O(n\log^2 n+m\log n)$。
空间复杂度：$O(n\log n+m)$。
:::
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 200005
namespace SGT{
struct Tree{
int l,r,min,cnt,tag1,tag2;
long long sum;
}tr[MAXN*4];
inline void update(int c){
tr[c].min=min(tr[c*2].min,tr[c*2+1].min);
tr[c].cnt=0;
if(tr[c*2].min==tr[c].min) tr[c].cnt+=tr[c*2].cnt;
if(tr[c*2+1].min==tr[c].min) tr[c].cnt+=tr[c*2+1].cnt;
tr[c].sum=tr[c*2].sum+tr[c*2+1].sum;
}
inline void tag1(int c,int k){
tr[c].min+=k;
tr[c].tag1+=k;
}
inline void tag2(int c,int k){
tr[c].sum+=1ll*k*tr[c].cnt;
tr[c].tag2+=k;
}
inline void down(int c){
if(tr[c].tag1){
tag1(c*2,tr[c].tag1);
tag1(c*2+1,tr[c].tag1);
tr[c].tag1=0;
}
if(tr[c].tag2){
if(tr[c*2].min==tr[c].min){
tag2(c*2,tr[c].tag2);
}
if(tr[c*2+1].min==tr[c].min){
tag2(c*2+1,tr[c].tag2);
}
tr[c].tag2=0;
}
}
void build(int c,int L,int R){
tr[c].l=L;tr[c].r=R;
if(L==R){
tr[c].cnt=1;
return ;
}
int mid=(L+R)>>1;
build(c*2,L,mid);
build(c*2+1,mid+1,R);
update(c);
}
void add(int c,int L,int R,int k){
if(tr[c].l>=L&&tr[c].r<=R){
tag1(c,k);
return ;
}
down(c);
int mid=(tr[c].l+tr[c].r)>>1;
if(L<=mid) add(c*2,L,R,k);
if(R>mid) add(c*2+1,L,R,k);
update(c);
}
inline void modify(){
if(tr[1].min==0){
tag2(1,1);
}
}
long long query(int c,int L,int R){
if(tr[c].l>=L&&tr[c].r<=R){
return tr[c].sum;
}
down(c);
int mid=(tr[c].l+tr[c].r)>>1;
long long ans=0;
if(L<=mid) ans+=query(c*2,L,R);
if(R>mid) ans+=query(c*2+1,L,R);
return ans;
}
}
int n,m,a[MAXN],fa[MAXN];
vector<int> e[MAXN];
int sz[MAXN],son[MAXN];
void dfs1(int u){
sz[u]=1;
int Max=0;
for(int v:e[u]){
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>Max){
Max=sz[v];
son[u]=v;
}
}
}
int dfn[MAXN],pos[MAXN],tot=0,top[MAXN];
void dfs2(int u,int t){
dfn[u]=++tot;
pos[tot]=u;
top[u]=t;
if(!son[u]) return ;
dfs2(son[u],t);
for(int v:e[u]){
if(v==son[u]) continue ;
dfs2(v,v);
}
}
struct Que{
int l,r,op,id;
};
vector<Que> q[MAXN];
void init(){
dfs1(1);
dfs2(1,1);
set<int> s;
auto calc=[&](int au,int aw){
auto it=s.upper_bound(au);
if(it!=s.end()){
int av=*it;
if(au<aw){
if(av<aw){
q[1].push_back({av,aw-1,1,0});
q[au+1].push_back({av,aw-1,-1,0});
}
}else{
q[aw+1].push_back({av,n,1,0});
q[au+1].push_back({av,n,-1,0});
}
}
it=s.lower_bound(au);
if(it!=s.begin()){
int av=*prev(it);
if(au>aw){
if(av>aw){
q[aw+1].push_back({au,n,1,0});
q[av+1].push_back({au,n,-1,0});
}
}else{
q[1].push_back({au,aw-1,1,0});
q[av+1].push_back({au,aw-1,-1,0});
}
}
};
dFor(i,n,1){
int u=pos[i];
for(int v:e[u]){
if(v==son[u]) continue ;
For(j,dfn[v],dfn[v]+sz[v]-1){
calc(a[pos[j]],a[u]);
}
For(j,dfn[v],dfn[v]+sz[v]-1){
s.insert(a[pos[j]]);
}
}
s.insert(a[u]);
if(u==top[u]){
For(j,dfn[u],dfn[u]+sz[u]-1){
s.erase(a[pos[j]]);
}
}
}
}
long long ans[MAXN];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
For(i,1,n){
cin>>a[i];
}
For(i,2,n){
cin>>fa[i];
e[fa[i]].push_back(i);
}
init();
For(i,1,m){
int l,r;
cin>>l>>r;
q[l-1].push_back({l,r,-1,i});
q[r].push_back({l,r,1,i});
ans[i]=-1ll*(r-l)*(r-l+1)/2;
}
SGT::build(1,1,n);
For(i,1,n){
for(auto [l,r,op,id]:q[i]){
if(id==0){
SGT::add(1,l,r,op);
}
}
SGT::modify();
for(auto [l,r,op,id]:q[i]){
if(id!=0){
ans[id]+=op*SGT::query(1,l,r);
}
}
}
For(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
:::
# 4
[P11364 [NOIP2024] 树上查询](https://www.luogu.com.cn/problem/P11364)
$n$ 个点的树，$m$ 次询问 $[l,r],k$，求
$$\max_{l\le L\le R\le r,R-L+1\ge k}dep_{LCA([L,R])}$$
:::success[Solution]
注意到结论
$$dep_{[l,r]}=\min_{i\in[l,r-1]}dep_{LCA(i,i+1)}$$
设 $a_i=dep_{LCA(i,i+1)}$，则
$$ans=\max_{l\le L\le R\le r,R-L+1\ge k}\min_{i\in[L,R-1]}a_i$$
对于 $k=1$ 就是区间最大值。
我们将每个区间 $[l,r]$ 视为一个点对，则考虑如何支配。
若 $l_1\le l_2\le r_2\le r_1,\min_{i\in[l_1,r_1]}a_i=\min_{i\in[l_2,r_2]}a_i$，则 $[l_1,r_1]$ 支配 $[l_2,r_2]$。
对于每个位置 $i$，单调栈找到左右侧第一个比它小的位置 $pre_i,suf_i$，则支配对为 $[pre_i+1,suf_i]$，一共 $O(n)$ 对。
问题转换为查询所有与查询区间支交长度 $\ge k$ 的支配对权值最大值。
正确性证明：虽然交不一定包含原最小值，但其实际更大的最小值一定被另一个支配对统计到，所以答案不会受影响。
我们将询问离线下来，考虑做二维数点，设查询为 $[l,r],k$，支配对为 $[x,y]$。
Case 1：
$$\begin{cases}x\le r-k+1\\y\ge r\end{cases}$$
对 $x$ 扫描线，$y$ 树状数组查询。
Case 2：
$$\begin{cases}x\le l\\y\ge l+k-1\end{cases}$$
对 $x$ 扫描线，$y$ 树状数组查询。
Case 3：
$$\begin{cases}l\le x\le r-k+1\\y-x+1\ge k\end{cases}$$
对 $y-x+1$ 扫描线，$x$ 线段树查询。
时间复杂度：$O(n\log n+m\log n)$。
空间复杂度：$O(n+m)$。
:::
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 500005
#define MAXM 20
int n;
vector<int> e[MAXN];
int dfn[MAXN],tot=0,dep[MAXN];
int f[MAXM][MAXN],lg[MAXN];
void dfs(int u,int fa){
dfn[u]=++tot;
f[0][tot]=fa;
dep[u]=dep[fa]+1;
for(int v:e[u]){
if(v==fa) continue ;
dfs(v,u);
}
}
inline int get(int x,int y){
return dfn[x]<dfn[y]?x:y;
}
inline int LCA(int x,int y){
if(x==y) return x;
x=dfn[x];
y=dfn[y];
if(x>y) swap(x,y);
x++;
int k=lg[y-x+1];
return get(f[k][x],f[k][y-(1<<k)+1]);
}
inline int qmax(int l,int r){
int k=lg[r-l+1];
return max(f[k][l],f[k][r-(1<<k)+1]);
}
int a[MAXN];
int pre[MAXN],suf[MAXN];
struct Que{
int x,y,op,id;
};
vector<Que> qx[MAXN],qk[MAXN];
void init(){
dfs(1,0);
For(i,2,n){
lg[i]=lg[i>>1]+1;
}
For(i,1,lg[n]){
For(j,1,n-(1<<i)+1){
f[i][j]=get(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
}
For(i,1,n-1){
a[i]=dep[LCA(i,i+1)];
}
For(i,1,n){
f[0][i]=dep[i];
}
For(i,1,lg[n]){
For(j,1,n-(1<<i)+1){
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
}
stack<int> s;
s.push(0);
For(i,1,n-1){
while(a[s.top()]>=a[i]) s.pop();
pre[i]=s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(n);
dFor(i,n-1,1){
while(a[s.top()]>=a[i]) s.pop();
suf[i]=s.top();
s.push(i);
}
For(i,1,n-1){
int x=pre[i]+1,y=suf[i];
qx[x].push_back({x,y,0,a[i]});
qk[y-x+1].push_back({x,y,0,a[i]});
}
}
int m,ans[MAXN];
namespace Bit{
int tr[MAXN];
void add(int x,int k){
while(x){
tr[x]=max(tr[x],k);
x-=x&-x;
}
}
int query(int x){
int ans=0;
while(x<=n){
ans=max(ans,tr[x]);
x+=x&-x;
}
return ans;
}
}
namespace SGT{
struct Tree{
int max;
}tr[MAXN*4];
inline void update(int c){
tr[c].max=max(tr[c*2].max,tr[c*2+1].max);
}
void modify(int c,int L,int R,int x,int k){
if(L==R){
tr[c].max=max(tr[c].max,k);
return ;
}
int mid=(L+R)>>1;
if(x<=mid) modify(c*2,L,mid,x,k);
else modify(c*2+1,mid+1,R,x,k);
update(c);
}
int query(int c,int L,int R,int l,int r){
if(l<=L&&r>=R){
return tr[c].max;
}
int mid=(L+R)>>1;
int ans=0;
if(l<=mid) ans=max(ans,query(c*2,L,mid,l,r));
if(r>mid) ans=max(ans,query(c*2+1,mid+1,R,l,r));
return ans;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
For(i,1,n-1){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
init();
cin>>m;
For(i,1,m){
int l,r,k;
cin>>l>>r>>k;
if(k==1){
ans[i]=qmax(l,r);
continue ;
}
qx[r-k+1].push_back({r-k+1,r,1,i});
qx[l].push_back({l,l+k-1,1,i});
qk[k].push_back({l,r-k+1,1,i});
}
For(x,1,n){
for(auto [x,y,op,id]:qx[x]){
if(op==0){
Bit::add(y,id);
}else{
ans[id]=max(ans[id],Bit::query(y));
}
}
}
dFor(k,n,1){
for(auto [x,y,op,id]:qk[k]){
if(op==0){
SGT::modify(1,1,n,x,id);
}else{
ans[id]=max(ans[id],SGT::query(1,1,n,x,y));
}
}
}
For(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
:::
# 5
[P9058 [Ynoi2004] rpmtdq](https://www.luogu.com.cn/problem/P9058)
$n$ 个点的树，$m$ 次询问 $[l,r]$，求
$$\min_{l\le i<j\le r}dis(i,j)$$
:::success[Solution]
点分治，对于每一层，设重心为 $r$，设 $d_u=dis(r,u)$。
考虑 $(l,r)$ 之间的支配关系。
对于 $l<u<r$，若 $(l,r)$ 为支配对，则
$$d_l+d_r<d_u+d_l,d_l+d_r<d_u+d_r$$
$$d_l<d_u,d_r<d_u$$
则 $(l,r)$ 为支配对的必要条件是
$$\max(d_l,d_r)<\min_{l<u<r}d_u$$
如果 $l,r$ 在同一子树内，那么它们会在下层被统计到，整个过程一定充分。需要注意的是不能在本层用 $d_l+d_r$ 来算 $dis$，需要特判掉。
我们找每个 $\max(l,r)$ 的较大者，则对于每个 $u$，其只会于其编号两侧第一个 $d_v\le d_u$ 的位置产生支配对，则共产生 $O(sz)$ 个支配对。排序后用单调栈查找即可。
总支配对数 $O(n\log n)$，查找时间复杂度 $O(n\log^2 n)$。
我们不要求枚举所有真正不可被任意点对支配的点对，只需要枚举一个充分不必要的候选集。
将询问离线，和找出的支配对做一遍扫描线，用树状数组维护。
时间复杂度：$O(n\log^2 n+m\log n)$。
空间复杂度：$O(n\log n+m)$。
:::
:::success[Code]
```cpp
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
#define MAXN 200005
#define MAXM 1000005
#define inf (1<<30)
#define INF (1ll<<60)
int n;
vector<pair<int,int>> e[MAXN];
bool vis[MAXN];
int sz[MAXN];
void dfs1(int u,int f){
sz[u]=1;
for(auto [v,w]:e[u]){
if(v==f||vis[v]) continue ;
dfs1(v,u);
sz[u]+=sz[v];
}
}
int all,Min,pos;
void dfs2(int u,int f){
int Max=all-sz[u];
for(auto [v,w]:e[u]){
if(v==f||vis[v]) continue ;
dfs2(v,u);
Max=max(Max,sz[v]);
}
if(Max<Min){
Min=Max;
pos=u;
}
}
vector<pair<int,long long>> a;
int c[MAXN],tot=0;
void dfs3(int u,int f,long long d){
c[u]=tot;
a.push_back({u,d});
for(auto [v,w]:e[u]){
if(v==f||vis[v]) continue ;
dfs3(v,u,d+w);
}
}
int st[MAXN],top=0;
struct Que{
int l,op;
long long id;
};
vector<Que> q[MAXN];
void find(){
sort(a.begin(),a.end());
top=0;
For(i,0,a.size()-1){
while(top&&a[st[top]].second>a[i].second) top--;
if(top){
int l=a[st[top]].first,r=a[i].first;
if(c[l]!=c[r]){
long long d=a[st[top]].second+a[i].second;
q[r].push_back({l,0,d});
}
}
st[++top]=i;
}
top=0;
dFor(i,a.size()-1,0){
while(top&&a[st[top]].second>a[i].second) top--;
if(top){
int l=a[i].first,r=a[st[top]].first;
if(c[l]!=c[r]){
long long d=a[i].second+a[st[top]].second;
q[r].push_back({l,0,d});
}
}
st[++top]=i;
}
}
void solve(int u){
dfs1(u,0);
all=sz[u];Min=inf;
dfs2(u,0);
u=pos;
a.clear();
tot=0;
c[u]=0;
a.push_back({u,0});
for(auto [v,w]:e[u]){
if(vis[v]) continue ;
tot++;
dfs3(v,u,w);
}
find();
vis[u]=1;
for(auto [v,w]:e[u]){
if(vis[v]) continue ;
solve(v);
}
}
int m;
long long ans[MAXM];
long long tr[MAXN];
void insert(int x,long long k){
while(x){
tr[x]=min(tr[x],k);
x-=x&-x;
}
}
long long query(int x){
long long ans=INF;
while(x<=n){
ans=min(ans,tr[x]);
x+=x&-x;
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
For(i,1,n-1){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
solve(1);
cin>>m;
For(i,1,m){
int l,r;
cin>>l>>r;
if(l==r){
ans[i]=-1;
continue ;
}
q[r].push_back({l,1,i});
}
For(i,1,n){
tr[i]=INF;
}
For(r,1,n){
for(auto [l,op,id]:q[r]){
if(op==0){
insert(l,id);
}else{
ans[id]=query(l);
}
}
}
For(i,1,m){
cout<<ans[i]<<'\n';
}
return 0;
}
```
:::