http://codeforces.com/gym/101889
I
先跑一遍最小生成树，把经过的边和答案记录下来
对于每个询问的边，显然如果处于MST中，答案不变
如果不在MST中，假设这条边连上了，那么就会和原本的MST形成环，删除这个环中权值最大的边就是答案
处理的时候，可以用LCA维护MST：给出边的两个节点u、v，那么u和v的LCA路径上的最大值边就是环中权值最大的边
代码：
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int MAX_V = 100005;
const int MAX_E = 200005;
const int MAX_N = 100005;
struct LCA_Online {
int N, M, E, root, in[MAX_N], head[MAX_N];
int f[MAX_N][30], c[MAX_N][30], depth[MAX_N];
struct Edge {
int to, next, cost;
} es[MAX_N << 2];
void addEdge(int u, int v, int w) {
es[E].to = v;
es[E].next = head[u];
es[E].cost = w;
head[u] = E++;
in[v]++;
}
void init(int N) {
this->N = N;
this->M = floor(log2(double(N)));
this->E = 0;
this->root = 0;
memset(head, -1, sizeof head);
memset(f, 0, sizeof f);
memset(c, 0, sizeof c);
memset(in, 0, sizeof in);
}
void dfs(int u) {
for (int j = 1; j <= M; j++) {
f[u][j] = f[f[u][j - 1]][j - 1];
c[u][j] = max(c[u][j - 1], c[f[u][j - 1]][j - 1]);
}
for (int i = head[u]; ~i; i = es[i].next) {
int v = es[i].to;
int w = es[i].cost;
if (v != f[u][0]) {
depth[v] = depth[u] + 1;
f[v][0] = u;
c[v][0] = w;
dfs(v);
}
}
}
void run() {
dfs(1);
}
int LCA(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
int res = 0;
int d = depth[u] - depth[v];
for (int i = 0; i <= M; i++) {
if ((1 << i) & d) {
res = max(res, c[u][i]);
u = f[u][i];
}
}
if (u == v) {
return res;
}
for (int i = M; i >= 0; i--) {
if (f[u][i] != f[v][i]) {
res = max(res, max(c[u][i], c[v][i]));
u = f[u][i];
v = f[v][i];
}
}
return max(res, max(c[u][0], c[v][0]));
}
} lca;
struct Kruskal {
struct Edge {
int from, to, cost;
bool operator< (const Edge& e) const {
return cost < e.cost;
}
} es[MAX_E];
int V, E, p[MAX_V];
void init(int V) {
this->V = V;
this->E = 0;
for (int i = 0; i < V; i++) {
p[i] = i;
}
}
void addEdge(int u, int v, int w) {
es[E].from = u;
es[E].to = v;
es[E].cost = w;
E++;
}
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void unite(int x, int y) {
p[find(y)] = find(x);
}
ll kruskal() {
ll sum = 0;
sort(es, es + E);
for (int i = 0; i < E; i++) {
Edge &e = es[i];
if (find(e.from) != find(e.to)) {
sum += e.cost;
unite(e.from, e.to);
lca.addEdge(e.from, e.to, e.cost);
lca.addEdge(e.to, e.from, e.cost);
}
}
return sum;
}
} kru;
map<pair<int, int>, int> cost;
int main() {
int N, R, Q;
scanf("%d%d", &N, &R);
kru.init(N);
lca.init(N);
for (int i = 0, u, v, w; i < R; i++) {
scanf("%d%d%d", &u, &v, &w);
if (u > v) {
swap(u, v);
}
cost[make_pair(u, v)] = w;
//cost[make_pair(v, u)] = w;
kru.addEdge(u, v, w);
//kru.addEdge(v, u, w);
}
ll ans = kru.kruskal();
lca.run();
scanf("%d", &Q);
while (Q--) {
int u, v;
scanf("%d%d", &u, &v);
if (u > v) {
swap(u, v);
}
printf("%I64d\n", ans + cost[make_pair(u, v)] - lca.LCA(u, v));
}
}