经过两天的努力终于码了出来

建议黑题

首先暴力的过程是把$[l,r]$中的边都提出来跑一遍最小生成树,但是这样肯定不行

结论

每一条代价为x的边一定存在一个代价下界y,满足对于询问的区间$[L,R]$,$y<L<=x,R>x$时一定会被算进去,y可以大于等于x

证明

感性理解,假设我们将边权从大到小加入,然后动态维护一颗最小生成树,那么会发现加入到边i的时候i因为i是此时最小的边,所以一定会被算上,同时随着时间再向前推移,总会有一个时间点(可能为0),i会因为不再优而被弹出

这个变化的过程是连续的,所以一定存在一个y,同时如果他一直没用则$y>x$,一直有用对应$y=0$

有了这个结论,假设求出了每条边的y,不难我们的问题就变成了一个二维数点问题

即支持

矩阵加
单点查询

其中单点查询$(L,R)$,矩阵加左下角$[y+1,y+1]$右上角$[x,\infty]$,我们可以使用二维差分实现

注意到题目强制在线,所以这个问题可以用主席树实现

现在我们如何求y呢?

其实直接模拟证明中的过程就是可以的!

因为一条边被删除的时刻,就是他被弹出时刻使其弹出的那条边的边权!

但是动态维护生成树,我们需要:

LCT!

故综上,我们用LCT来求出每条边的y,再用主席树完成二维数点即可

题意补充:

强制在线方式:即lst为上次询问的答案,这次询问的l,r需要减去lst(题目中的letax不知道为啥是加?也可能是我英语太菜了)

细节补充

1. 清空的时候都要清空,小心二维差分数组没清空
2. 非常重要的一点是:

一般的题目中重边是没用的,而我们这个题重边是相当有用的!

而如果原本u,v间就有边了,再加入一条边会导致重边成环!

而显然的是用LCT寻找是找不到这种情况的!!

所以我们要特判掉,特判有些坑/xyx

3. 权值要离散化,然后把询问离散回来,而且左右端点离散结果还不一样.....
4. 建立主席树,我使用了每个版本只新建一个节点的写法,因为对于一个时刻可能有多个修改....具体可以看代码

3,4都是因为本题恶心的125mb空间限制(

下面是ACcode:

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define se second
#define fi first
#define mkp(x,y) (make_pair(x,y))
#define pii pair<int,int>
const int MAXN = 1e3 + 7;
const int MAXW = 2e5 + 7;
const int MAXM = 2e5 + 7;
const int MAXT = 4e6 + 7;
using namespace std;
int n, m, q;
struct rec {
	int x, y, z, w, k;
	bool operator<(const rec &X)const {
		return w < X.w;
	}
} e[MAXM];
namespace LoveJY_Catalan_Tmd {
#define L (ch[x][0])
#define R (ch[x][1])
	int ch[MAXM][2], f[MAXM], tag[MAXM], st[MAXM];
	int a[MAXM], id[MAXM];//子树中最大标号是啥
	inline bool nroot(int x) {
		return ch[f[x]][0] == x || ch[f[x]][1] == x;
	}
	inline void pushup(int x) {
		id[x] = a[id[L]] < a[id[R]] ? id[L] : id[R];
		id[x] = a[x] < a[id[x]] ? x : id[x];
	}
	inline void pushR(int x) {
		tag[x] ^= 1;
		L ^= R ^= L ^= R;
	}
	inline void pushdown(int x) {
		if(tag[x]) {
			if(L)pushR(L);
			if(R)pushR(R);
			tag[x] = 0;
		}
	}
	inline void rotate(int x) {
		int y = f[x], z = f[y], k = ch[y][1] == x, w = ch[x][!k];
		if(nroot(y))ch[z][ch[z][1] == y] = x;
		ch[x][!k] = y;
		ch[y][k] = w;
		f[y] = x;
		f[x] = z;
		if(w)f[w] = y;
		pushup(y);
	}
	inline void splay(int x) {
		int y = x, z = 0;
		st[++z] = y;
		while(nroot(y)) {
			st[++z] = f[y];
			y = f[y];
		}
		while(z) {
			pushdown(st[z]);
			z--;
		}
		while(nroot(x)) {
			y = f[x];
			z = f[y];
			if(nroot(y)) {
				rotate((ch[x][0] == y) ^ (ch[z][0] == y) ? y : x);
			}
			rotate(x);
		}
		pushup(x);
	}
	inline void access(int x) {
		for(int y = 0; x; x = f[y = x]) {
			splay(x); R = y; pushup(x);
		}
	}
	inline void makeroot(int x) {
		access(x);
		splay(x);
		pushR(x);
	}
	inline int findroot(int x) {
		access(x);
		splay(x);
		while(L)pushdown(x), x = L;
		splay(x);
		return x;
	}
	inline void split(int x, int y) {
		makeroot(x);
		access(y);
		splay(y);
	}
	inline void link(int x, int y) {//把y接到x上去
		makeroot(x);
		makeroot(y);
		f[y] = x;
	}
	inline void cut(int x, int y) {
		split(x, y);
		ch[y][0] = 0;
		f[x] = 0;
		pushup(y);
	}
#undef L
#undef R
}
using namespace LoveJY_Catalan_Tmd;
int mx;
vector<int> zhq;
inline int getid(int x) {
	return lower_bound(zhq.begin(), zhq.end(), x) - zhq.begin() + 1;
}
inline void init3() {
	for(int i = 1; i <= m; ++i) {
		zhq.pb(e[i].w);
	}
	sort(zhq.begin(), zhq.end());
	zhq.erase(unique(zhq.begin(), zhq.end()), zhq.end());
	for(int i = 1; i <= m; ++i) {
		e[i].k = e[i].w;
		e[i].w = getid(e[i].w);
	}
	return ;
}
int mp[MAXN][MAXN];
inline void init2() {
	sort(e + 1, e + m + 1);
	a[0] = 1e9 + 1;
	for(int i = 1; i <= n; ++i)a[i] = 1e9;
	for(int i = 1; i <= m; ++i) {
		int u = e[i].x;
		int v = e[i].y;
		mx = max(mx, e[i].w);
		if(u > v)swap(u, v);
		if(mp[u][v]) {
			e[i].z = a[mp[u][v]];
			a[mp[u][v]] = e[i].w;
			access(mp[u][v]);
			splay(mp[u][v]);
			continue;
		}
		makeroot(u);
		if(findroot(v) != u) {
			a[i + n] = e[i].w;
			link(i + n, u);
			link(i + n, v);
			e[i].z = 0;
			mp[u][v] = i + n;
		} else {
			split(u, v);
			int qwq = id[v];
			e[i].z = a[qwq];
			a[qwq] = 1e9;
			cut(qwq, e[qwq - n].x);
			cut(qwq, e[qwq - n].y);
			mp[e[qwq - n].x][e[qwq - n].y] = 0;
			a[i + n] = e[i].w;
			link(i + n, u);
			link(i + n, v);
			mp[u][v] = i + n;
		}
	}
	return ;
}
int T2;
int ls[MAXT], rs[MAXT], root[MAXW];
ll tr[MAXT];
#define fi first
#define se second
#define mid ((l+r)>>1)
vector<pii> v[MAXW];
inline void add(int &x, int y, int l, int r, int P, int V) {
	if(x == y || !x) {
		x = ++T2;
		tr[x] = tr[y];
		ls[x] = ls[y];
		rs[x] = rs[y];
	}
	tr[x] += V;
	if(l == r) {
		return ;
	}
	if(P <= mid)add(ls[x], ls[y], l, mid, P, V);
	else add(rs[x], rs[y], mid + 1, r, P, V);
}

inline ll qry(int k, int l, int r, int L, int R) {
	if(!k)return 0;
	if(L <= l && r <= R) {
		return tr[k];
	}
	if(R <= mid)return qry(ls[k], l, mid, L, R);
	else if(L > mid)return qry(rs[k], mid + 1, r, L, R);
	else return qry(ls[k], l, mid, L, R) + qry(rs[k], mid + 1, r, L, R);
}

inline void init() {
	for(int i = 1; i <= m; ++i) {
		if(e[i].z + 1 > e[i].w)continue;//剪 枝
		if(e[i].z + 1 <= mx)
			v[e[i].z + 1].pb(mkp(e[i].w, e[i].k));
		if(e[i].w + 1 <= mx)
			v[e[i].w + 1].pb(mkp(e[i].w, -e[i].k));
	}
	for(int i = 1; i <= mx; ++i) {
		if(v[i].size() == 0) {
			root[i] = root[i - 1];
			continue;
		}
		for(auto e : v[i])add(root[i], root[i - 1], 1, mx, e.fi, e.se);
		v[i].clear();
	}
	return;
}
inline void clear() {
	T2 = 0;
	mx = 0;
	memset(root, 0, sizeof(root));
	memset(tag, 0, sizeof(tag));
	memset(ch, 0, sizeof(ch));
	memset(f, 0, sizeof(f));
	memset(id, 0, sizeof(id));
	memset(ls, 0, sizeof(ls));
	memset(rs, 0, sizeof(rs));
	memset(tr, 0, sizeof(tr));
	memset(mp, 0, sizeof(mp));
	memset(e, 0, sizeof(e));
	zhq.clear();
}
int T;
int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= m; ++i) {
			scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
			if(e[i].x > e[i].y)swap(e[i].x, e[i].y);
		}
		init3();
		init2();//预处理主席树呢
		init();//把所有的拿出来跑lct
		scanf("%d", &q);
		ll ans = 0, x, y;
		for(int i = 1; i <= q; ++i) {
			scanf("%lld%lld", &x, &y);
			x -= ans;
			y -= ans;
			x = getid(x);
			y = upper_bound(zhq.begin(), zhq.end(), y) - zhq.begin();
			if(y < x || x > mx)ans = 0;
			else ans = qry(root[x], 1, mx, 1, y);
			printf("%lld\n", ans);
		}
		clear();
	}
	return 0;
}