int n; char s[maxn]; unsignedlonglong h[maxn], p[maxn]; int mi[maxn][maxn], ml[maxn][maxn], mt[maxn][maxn], res[maxn][maxn];
unsignedlonglongget(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1]; }
intsolve(int l, int r){ if (r - l + 1 <= 4) return r - l + 1; if (res[l][r]) return res[l][r]; res[l][r] = r - l + 1; for (int i = l; i <= r; i++) { for (int len = 1; i + len * 2 - 1 <= r; len++) { unsignedlonglong h1 = get(i, i + len - 1); for (int t = 2; i + len * t - 1 <= r; t++) { unsignedlonglong h2 = get(i + len * (t - 1), i + len * t - 1); if (h2 != h1) break; int tmp1 = solve(i + len * t, r); int tmp2 = solve(i, i + len - 1); int tmp3 = len < 10 ? 3 : (len < 100 ? 4 : 5); int tmp4 = i - l; if (tmp1 + tmp2 + tmp3 + tmp4 < res[l][r]) { mi[l][r] = i, ml[l][r] = len, mt[l][r] = t, res[l][r] = tmp1 + tmp2 + tmp3 + tmp4; } } } } return res[l][r]; }
voidprint(int l, int r){ if (mi[l][r] == 0) { for (int i = l; i <= r; i++) putchar(s[i]); return; } for (int i = l; i < mi[l][r]; i++) putchar(s[i]); printf("%d", mt[l][r]); putchar('('); print(mi[l][r], mi[l][r] + ml[l][r] - 1); putchar(')'); print(mi[l][r] + ml[l][r] * mt[l][r], r); }
int f[maxn]; intfind(int x){ return x == f[x] ? x : f[x] = find(f[x]); }
voidmerge(int u, int v, int w){ u = find(u); v = find(v); if (u == v) return; if (st[u].size() < st[v].size()) swap(u, v); //启发式合并 f[v] = u; for (int x : st[v]) { if (st[u].count(x)) { ans[x] = w; st[u].erase(x); } else st[u].insert(x); } st[v].clear(); }
intmain(){ // freopen("cost.in", "r", stdin); // freopen("cost.out", "w", stdout); read(n); read(m); for (int i = 1; i <= m; i++) { read(e[i].u); read(e[i].v); read(e[i].w); } sort(e + 1, e + m + 1, compare); read(q); for (int i = 1; i <= q; i++) { int u, v; read(u); read(v); st[u].insert(i); st[v].insert(i); } for (int i = 1; i <= n; i++) f[i] = i; for (int i = 1; i <= m; i++) merge(e[i].u, e[i].v, e[i].w); for (int i = 1; i <= q; i++) write(ans[i]); return0; }