贴一下使用dsu和lca的代码，dsu的代码很简单，可以马上写出来，但是lca的代码就不熟练了。这里lca的计算还是用了dfs的访问时间标记，我想起来割边， 割点的判断， dfu[u], low[u],的的使用，还有lca的离线算法，tarjan算法，然后又查到了求强连通分量的算法，也是使用访问时间标记，这些算法，有时间好好整理一下。dfs判断回路。等等。想起来再补充。

 

1 #include
     
        2 #define pb push_back  3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)  4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl  5 typedef long long ll;  6 using namespace std;  7 typedef pair
      
        pii;  8 const int maxn = 2e5 + 10;  9 const int inf = 1e9 + 7; 10 int n, m; 11 int w[maxn], c[maxn], a[maxn], b[maxn]; 12 // dsu disjoint set union //find and union 13 int sz[maxn], p[maxn]; 14 void init() { 15     for (int i = 1; i <= n; i++) { 16         sz[i] = 1; p[i] = i; 17     } 18 } 19 int get(int x) { 20     if(x == p[x]) return x; 21     return p[x] = get(p[x]); 22 } 23 bool unite(int x, int y) { 24     x = get(x); y = get(y); 25     if(x == y) return 0; 26     if(sz[x] > sz[y]) swap(x, y); 27     sz[y] += sz[x]; 28     p[x] = y; 29     return 1; 30 } 31  32 struct node { 33     int to, idx, w; 34     node(int to, int idx, int w) : to(to), idx(idx), w(w) {} 35 }; 36  37 vector
       
         g[maxn]; 38 int depth[maxn]; 39 bool used[maxn]; 40 pii fmaxi[maxn][20]; 41 int tin[maxn], tout[maxn], timer; 42 int fup[maxn][20]; 43 void dfs(int v, int p, int wup, int eidx, int dep) { 44     tin[v] = ++timer; 45     fup[v][0] = p; 46     fmaxi[v][0] = {wup, eidx}; 47     depth[v] = dep; 48     for (int i = 1; i < 20; i++) { 49         fup[v][i] = fup[fup[v][i - 1] ][i - 1]; 50         fmaxi[v][i] = max(fmaxi[v][i - 1], fmaxi[fup[v][i - 1] ][i - 1]); 51     } 52     for (auto it : g[v]) { 53         int to = it.to; 54         int idx = it.idx; 55         int w = it.w; 56         if(to == p) continue; 57         dfs(to, v, w, idx, dep + 1); 58     } 59     tout[v] = ++timer; 60 } 61  62 bool isAncestor(int x, int y) { 63     return tin[x] <= tin[y] && tout[x] >= tout[y]; 64 } 65 int lca(int x, int y) { 66     if(isAncestor(x, y)) return x; 67     if(isAncestor(y, x)) return y; 68     for (int i = 20 - 1; i >= 0; i--) { 69         if(!isAncestor(fup[x][i], y)) x = fup[x][i]; 70     } 71     return fup[x][0]; 72 } 73 pii getfmax1(int x, int p) { 74     int len = depth[x] - depth[p]; 75     pii res = {-inf, -inf}; 76     for (int i = 20 - 1; i >= 0; i--) { 77         if((len >> i) & 1) { 78             len ^= (1 << i); 79             res = max(res, fmaxi[x][i]); 80             x = fup[x][i]; 81         } 82     } 83     return res; 84 } 85 pii getfmax(int x, int y) { 86     int z = lca(x, y); 87     return max(getfmax1(x, z), getfmax1(y, z)); 88 } 89 int S; 90 ll sum; 91 int perm[maxn]; 92 void solve() { 93     cin >> n >> m; 94     init(); 95     for (int i = 1; i <= m; i++) cin >> w[i]; 96     for (int i = 1; i <= m; i++) cin >> c[i]; 97     for (int i = 1; i <= m; i++) cin >> a[i] >> b[i]; 98     cin >> S; 99     for (int i = 1; i <= m; i++)100         perm[i] = i;101     sort(perm + 1, perm + m + 1, [](int i, int j) {
   return w[i] < w[j];});102     vector
        
          e;103     for (int j = 1; j <= m; j++) {104         int i = perm[j];105         if(unite(a[i], b[i])) {106             e.pb(i);107             sum += w[i];108         }109     }110     //cout << sum << endl;111     assert((int)e.size() == n - 1);112     for (int idx : e) {113         g[a[idx] ].pb({b[idx], idx, w[idx] });114         g[b[idx] ].pb({a[idx], idx, w[idx] });115     }116     dfs(1, 1, -inf, -inf, 0);117     pair
         
           best = {(ll)1e18, {-1, -1}};118     for (int idx = 1; idx <= m; idx++) {119         pii z = getfmax(a[idx], b[idx]);120         ll nsum = sum - z.first + w[idx] - (S / c[idx]);121         pair
          
            cur = {nsum, {z.second, idx} };122 best = min(best, cur);123 }124 assert(best.second.first != -1);125 cout << best.first << endl;126 for (int idx : e) {127 used[idx] = 1;128 }129 used[best.second.first] = 0;130 used[best.second.second] = 1;131 for (int i = 1; i <= m; i++) {132 if(used[i]) {133 cout << i << " ";134 int ww = w[i];135 if(i == best.second.second)136 ww -= S / c[i];137 cout << ww << endl;138 }139 }140 141 }142 143 int main() {144 //freopen("test.in", "r", stdin);145 //freopen("test.out", "w", stdout);146 solve();147 return 0;148 }149 150 void dfs2(int x, int lt) {151 fup[x][0] = lt;152 for (auto it : g[x]) {153 int to = it.to;154 int idx = it.idx;155 if(to == lt) continue;156 fmaxi[to][0] = {w[idx], idx};157 depth[to] = depth[x] + 1;158 dfs2(to, x);159 }160 }161 void build(int root) {162 dfs2(1, 1);163 for (int i = 1; i <= 18; i++) {164 for (int x = 1; x <= n; x++) {165 fup[x][i] = fup[fup[x][i - 1] ][i - 1];166 fmaxi[x][i] = max(fmaxi[fup[x][i - 1] ][i - 1], fmaxi[x][i - 1] );167 168 }169 }170 }171 int adv(int x, int v, pii & ret) {172 for (int i = 0; (1 << i) <= v; i++) {173 if((v >> i) & 1) {174 ret = max(ret, fmaxi[x][i]);175 x = fup[x][i];176 }177 }178 return x;179 }180 pii lca2(int x, int y) {181 pii ret = {-1, -1};182 if(depth[x] > depth[y]) x = adv(x, depth[x] - depth[y], ret);183 else y = adv(y, depth[y] - depth[x], ret);184 if(x == y) return ret;185 for (int i = 17; i >= 0; i--) {186 if(fup[x][i] != fup[y][i]) {187 ret = max(ret, fmaxi[x][i]);188 ret = max(ret, fmaxi[y][i]);189 x = fup[x][i];190 y = fup[y][i];191 }192 }193 ret = max(ret, fmaxi[x][0]);194 ret = max(ret, fmaxi[y][0]);195 return ret;196 }