我们把边按权值从大到小依次加入图中
如果加到边权$V$，则当前的最小生成森林中边权$v\in[V, V']$(其中$V'$是任意值)形成的森林的边权和就是对于询问$[V, V']$的答案
由于点数不多，所以可以每次暴力$dfs$找环上最大边以及暴力删除。。。
又由于是强制在线，于是用可持久化线段树维护不同权值的出现次数即可
/**************************************************************
Problem: 4046
User: rausen
Language: C++
Result: Accepted
Time:8788 ms
Memory:46132 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = 1e3 + ;
const int M = 1e5 + ;
const int maxV = 1e6 + ; int read(); struct Edge {
int x, y, v; inline bool operator < (const Edge &e) const {
return v > e.v;
} inline void get() {
x = read(), y = read(), v = read();
}
} E[M]; struct edge {
int next, to, v;
edge() {}
edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}
} e[M << ]; struct chair_tree {
chair_tree *ls, *rs;
int sum; #define Cnt 3500000
inline void* operator new(size_t, chair_tree *_c = NULL, int f = ) {
static chair_tree mempool[Cnt], *c;
if (f) c = mempool;
if (_c == NULL)
c -> ls = c -> rs = NULL, c -> sum = ;
else *c = *_c;
return c++;
}
#undef Cnt #define mid (l + r >> 1)
void modify(int l, int r, int pos, int d) {
sum += d;
if (l == r) return;
if (pos <= mid) {
ls = new(ls)chair_tree;
ls -> modify(l, mid, pos, d);
} else {
rs = new(rs)chair_tree;
rs -> modify(mid + , r, pos, d);
}
} int query(int l, int r, int L, int R) {
if (L <= l && r <= R) return sum;
int res = ;
if (ls && L <= mid) res += ls -> query(l, mid, L, R);
if (rs && mid < R) res += rs -> query(mid + , r, L, R);
return res;
}
#undef mid
} *root[M]; int n, m, ans;
int first[N], tot;
int fa[N];
int tmp[M], len; inline void Add_Edges(int x, int y, int v) {
e[++tot] = edge(first[x], y, v), first[x] = tot;
e[++tot] = edge(first[y], x, v), first[y] = tot;
} #define y e[x].to
inline void Delete_Edge(int p, int q) {
int x;
if (e[first[p]].to == q) {
first[p] = e[first[p]].next;
return;
}
for (x = first[p]; x; x = e[x].next)
if (e[e[x].next].to == q) {
e[x].next = e[e[x].next].next;
return;
}
} inline void Delete_Edges(int p, int q) {
Delete_Edge(p, q);
Delete_Edge(q, p);
} int find_max(int p, int fa, int tar) {
int x, tmp;
for (x = first[p]; x; x = e[x].next)
if (y != fa) {
if (y == tar) return x;
tmp = find_max(y, p, tar);
if (tmp != -) {
if (e[tmp].v > e[x].v) return tmp;
return x;
}
}
return -;
}
#undef y int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
} inline int get(int x) {
return lower_bound(tmp + , tmp + len + , x) - tmp;
} int main() {
int T, now, i, x, y, Q;
for (T = read(); T; --T) {
n = read(), m = read(), ans = ;
for (i = ; i <= n; ++i) fa[i] = i;
for (i = ; i <= m; ++i) {
E[i].get();
tmp[i] = E[i].v;
}
sort(E + , E + m + );
sort(tmp + , tmp + m + ), len = unique(tmp + , tmp + m + ) - tmp - ;
memset(first, , sizeof(first)), tot = ; root[len + ] = new(NULL, )chair_tree;
for (now = len, i = ; now; --now) {
root[now] = new(root[now + ])chair_tree;
for (; E[i].v == tmp[now] && i <= m; ++i) {
x = find(E[i].x), y = find(E[i].y);
if (x != y) fa[x] = y;
else {
x = find_max(E[i].x, , E[i].y);
Delete_Edges(e[x].to, e[x ^ ].to);
root[now] -> modify(, len, get(e[x].v), -e[x].v);
}
Add_Edges(E[i].x, E[i].y, E[i].v);
root[now] -> modify(, len, get(E[i].v), E[i].v);
}
}
for (Q = read(); Q; --Q) {
x = read(), y = read();
x = upper_bound(tmp + , tmp + len + , x - ans - ) - tmp;
y = upper_bound(tmp + , tmp + len + , y - ans) - tmp - ;
if (x > y) printf("%d\n", ans = );
else printf("%d\n", ans = root[x] -> query(, len, x, y));
}
}
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}