讲一下部分分：
- 子任务 1：直接每次暴力做即可。
- 子任务 2：一条链，线段树单点修改 + 维护区间最小值，加上二分。
- 子任务 3：不会。
- 子任务 4：没有修改，维护原图的一棵 Kruskal 重构树即可。
- 子任务 5：不会。
接下来讲正解。
发现这个数据范围正好可以根号跑过，于是想到分块。
将操作分块，并将每一块中的边分成在块中不会被修改和会被修改的两类。
前一类边可以直接按边权从大到小加入，用并查集维护连通性和 (size)。
后一类边我们可以对于每一次询问暴力扫，看是否可以被加入，整个过程还需要使用可撤销并查集。
具体实现细节见代码。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
template <typename T>
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 100003, M = N << 1;
const int SZ = 500;
int n, m, q;
int tot;
int fa[N], sz[N];
int nid[N]; //old id
int val[N]; //edge's value
int ans[N];
struct UnionFind {int u, v;} stk[N]; int tp; //a stack of dsu
struct Node {int u, v, w, id;} a[M], p[M], g[M], tmp[M];
struct Query {int ty, x, y, id;} o[M], t1[M], t2[M];
bool vis[M]; //is modify?
inline bool cmp(Node x, Node y) {return x.w == y.w ? x.id < y.id : x.w > y.w;}
inline bool cmp1(Query x, Query y) {return x.y == y.y ? x.id < y.id : x.y > y.y;}
int getf(int u) {return fa[u] == u ? u : getf(fa[u]);}
inline void unionn(int u, int v)
{
int fu = getf(u), fv = getf(v);
if (fu == fv) return;
if (sz[fu] > sz[fv]) swap(fu, fv);
stk[++tp] = {fu, fv};
fa[fu] = fv, sz[fv] += sz[fu];
}
inline void Back() {int u = stk[tp].u, v = stk[tp].v; sz[v] -= sz[u], fa[u] = u, --tp;}
inline void solve()
{
int tp1 = 0, tp2 = 0; tp = 0;
for (int i = 1; i <= m; i+=1) vis[i] = false, nid[a[i].id] = i;
for (int i = 1; i <= n; i+=1) sz[i] = 1, fa[i] = i;
for (int i = 1; i <= tot; i+=1)
if (o[i].ty == 1) vis[o[i].x] = true, t1[++tp1] = o[i];
else t2[++tp2] = o[i];
sort(t2 + 1, t2 + 1 + tp2, cmp1);
int now = 1;
for (int i = 1; i <= tp2; i+=1)
{
while (now <= m && a[now].w >= t2[i].y)
{
if (!vis[a[now].id]) unionn(a[now].u, a[now].v);
++now;
}
int nowtp = tp;
for (int j = 1; j <= tp1; j+=1) val[t1[j].x] = a[nid[t1[j].x]].w;
for (int j = 1; j <= tp1; j+=1)
if (t1[j].id < t2[i].id) val[t1[j].x] = t1[j].y;
for (int j = 1; j <= tp1; j+=1)
if (val[t1[j].x] >= t2[i].y)
unionn(a[nid[t1[j].x]].u, a[nid[t1[j].x]].v);
ans[t2[i].id] = sz[getf(t2[i].x)];
while (tp > nowtp) Back();
}
for (int i = 1; i <= tp1; i+=1) a[nid[t1[i].x]].w = t1[i].y;
int nl = 0, nr = 0;
for (int i = 1; i <= m; i+=1)
if (vis[a[i].id]) p[++nl] = a[i];
else g[++nr] = a[i];
sort(p + 1, p + 1 + nl, cmp);
int i = 1, j = 1, cnt = 0;
while (i <= nl && j <= nr)
if (p[i].w >= g[j].w) a[++cnt] = p[i++];
else a[++cnt] = g[j++];
while (i <= nl) a[++cnt] = p[i++];
while (j <= nr) a[++cnt] = g[j++];
return;
}
int main()
{
n = gi <int> (), m = gi <int> ();
for (int i = 1; i <= m; i+=1)
a[i].u = gi <int> (), a[i].v = gi <int> (), a[i].w = gi <int> (), a[i].id = i;
sort(a + 1, a + 1 + m, cmp);
q = gi <int> ();
for (int i = 1; i <= q; i+=1)
{
++tot;
o[tot].ty = gi <int> (), o[tot].x = gi <int> (), o[tot].y = gi <int> (), o[tot].id = i;
if (tot == SZ) solve(), tot = 0;
}
if (tot) solve();
for (int i = 1; i <= q; i+=1) if (ans[i]) printf("%d
", ans[i]);
return 0;
}