有一幅$n$个点$m$条边的图，以及$q$个询问，每次询问边权为$[l,r]$的边组成的图中，可以互相到达的点对最多的图的边权和的最小值。强制在线。
$n \leq 1000,~m\leq 1e5,~q\leq 1e6$
差点就带着可持久化并查集直接上了。。
良心的说，这题算是涨姿势题。
考虑到最小生成树的性质，如果从小到大加边，那么不会有边被弹掉，换而言之，边权大小都是从最小值开始的。
但是，如果换种方式加边，就可以得到边权$\geq x$的图。再套个主席树，即可在$\log n$的时间里完成查询。
这题的数据范围也很奥妙啊，明显是让你暴力加边。为了保证复杂度是$n\times m$，瞎比搞了个链表来维护每次删边前的边。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int M=1e3+5;
const int N=4e6+5;
typedef long long ll;
typedef vector<int> vec;
#define pb push_back
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
template<class T>void rd(T &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
struct slide{
int u,v,c;
inline bool operator < (const slide &tmp)const{
return c>tmp.c;
}
}Slid[(int)1e5+5];
int n,m,s,pos[(int)1e5+5],B[(int)1e5+5];
template<class T>void nt(T x){
if(!x)return;
nt(x/10);
putchar(48+x%10);
}
template<class T>void pt(T x){
if(x)nt(x);
else putchar(48);
}
struct Chairman_Tree{
int ls[N],rs[N],cnt[N],allc;
ll sum[N];
inline void clear(){
for(int i=0;i<=allc;++i)
ls[i]=rs[i]=cnt[i]=sum[i]=0;
allc=0;
}
inline void up(int &rt){
sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
inline void update(int &rt,int ot,int k,int x,int l=1,int r=s){
if(rt==ot)rt=++allc,ls[rt]=ls[ot],rs[rt]=rs[ot],cnt[rt]=cnt[ot]+x;
else cnt[rt]+=x;
if(l==r){
sum[rt]=cnt[rt]*B[l-1];
return;
}
int mid=l+r>>1;
if(k<=mid)update(ls[rt],ls[ot],k,x,l,mid);
else update(rs[rt],rs[ot],k,x,mid+1,r);
up(rt);
}
inline ll query(int rt,int l,int r,int L=1,int R=s){
if(l==L&&r==R)return sum[rt];
int mid=L+R>>1;
if(r<=mid)return query(ls[rt],l,r,L,mid);
if(l>mid)return query(rs[rt],l,r,mid+1,R);
return query(ls[rt],l,mid,L,mid)+query(rs[rt],mid+1,r,mid+1,R);
}
}ct;
struct Link{
struct node{
int pre,nxt;
}ele[(int)1e5+5];
int allc,ed;
inline void clear(){
allc=ed=ele[0].nxt=0;
}
inline void add(int id){
ele[ed].nxt=id,ele[id].pre=ed;
ed=id,ele[ed].nxt=0;
}
inline void del(int id){
ele[ele[id].pre].nxt=ele[id].nxt;
ele[ele[id].nxt].pre=ele[id].pre;
}
}lk;
int f[M],cnt,rt[(int)1e5+5],beg[(int)1e5+5];
inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
vec G[(int)1e5+5];
inline void Init(){
memset(rt,cnt=0,sizeof(rt));
ct.clear(),lk.clear();
for(int i=1;i<=s;++i)
G[i].clear();
}
inline void Insert(int id,int r){
pos[id]=r,rt[id]=rt[id-1];
for(int i=1;i<=n;++i)f[i]=i;
lk.add(id);
ct.update(rt[id],rt[id-1],Slid[r].c,1);
for(int v=lk.ed;v;v=lk.ele[v].pre){
int c=pos[v];
int f1=find(Slid[c].u),f2=find(Slid[c].v);
if(f1==f2){
ct.update(rt[id],rt[id-1],Slid[c].c,-1);
lk.del(v);
}
else f[f2]=f1;//
}
}
inline void gao(){
cin>>n>>m;
Init();
for(int i=1,a,b,c;i<=m;++i){
rd(a),rd(b),rd(c),B[i-1]=c;
Slid[i]=(slide){a,b,c};
}
sort(B,B+m);
s=unique(B,B+m)-B;
for(int i=1;i<=m;++i){
Slid[i].c=lower_bound(B,B+s,Slid[i].c)-B+1;
G[Slid[i].c].pb(i);
}
for(int i=s;i;--i){
for(int j=0;j<G[i].size();++j)
Insert(cnt+j+1,G[i][j]);
cnt+=G[i].size();
beg[i]=cnt;
}
int q;cin>>q;
for(ll l,r,lastans=0;q--;){
rd(l),rd(r);
l-=lastans,r-=lastans;
int L=lower_bound(B,B+s,l)-B+1;
int R=upper_bound(B,B+s,r)-B;
if(R<L||L>s)lastans=0;
else lastans=ct.query(rt[beg[L]],1,R);
pt(lastans),putchar('\n');
}
}
int main(){
int _;
for(cin>>_;_--;)gao();
return 0;
}