Educational Codeforces Round 3 E. Minimum spanning tree for each edge (最小生成树+树链剖分)

题目链接：http://codeforces.com/contest/609/problem/E

给你n个点，m条边。

问枚举每条边，问你加这条边的前提下组成生成树的权值最小的树的权值和是多少。

先求出最小生成树，树链剖分一下最小生成树。然后枚举m条边中的每条边，要是这条边是最小生成树的其中一边，则直接输出最小生成树的答案；否则就用树剖求u到v之间的最大边，然后最小生成树权值减去求出的最大边然后加上枚举的这条边就是答案。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef __int64 LL;
  4 const int MAXN = 2e5 + 5;
  5 struct data {
  6     int from , to , index;
  7     bool flag;
  8     LL cost;
  9     bool operator <(const data& cmp) const {
 10         return cost < cmp.cost;
 11     }
 12 }a[MAXN] , b[MAXN];
 13 struct EDGE {
 14     int next , to;
 15     LL cost;
 16 }edge[MAXN << 2];
 17 int head[MAXN] , tot;
 18 int par[MAXN] , dep[MAXN] , son[MAXN] , size[MAXN];
 19 int top[MAXN] , id[MAXN] , cnt;
 20 
 21 bool cmp(const data& a , const data &b) {
 22     return a.index < b.index;
 23 }
 24 
 25 void init(int n) {
 26     memset(head , -1 , sizeof(head));
 27     for(int i = 1 ; i <= n ; ++i)
 28         par[i] = i;
 29 }
 30 
 31 int Find(int u) {
 32     if(par[u] == u)
 33         return u;
 34     return par[u] = Find(par[u]);
 35 }
 36 
 37 inline void add(int u , int v , LL cost) {
 38     edge[tot].to = v;
 39     edge[tot].next = head[u];
 40     edge[tot].cost = cost;
 41     head[u] = tot++; 
 42 }
 43 
 44 LL mst(int m) {
 45     LL sum = 0;
 46     int f = 0;
 47     for(int i = 1 ; i <= m ; ++i) {
 48         int u = Find(a[i].from) , v = Find(a[i].to);
 49         if(u != v) {
 50             par[u] = v;
 51             sum += a[i].cost;
 52             a[i].flag = true;
 53             add(a[i].from , a[i].to , a[i].cost);
 54             add(a[i].to , a[i].from , a[i].cost);
 55             ++f;
 56             b[f].from = a[i].from , b[f].to = a[i].to , b[f].cost = a[i].cost;
 57         }
 58         else {
 59             a[i].flag = false;
 60         }
 61     }
 62     return sum;
 63 }
 64 
 65 void dfs1(int u , int p , int d) {
 66     dep[u] = d , par[u] = p , son[u] = u , size[u] = 1;
 67     for(int i = head[u] ; ~i ; i = edge[i].next) {
 68         int v = edge[i].to;
 69         if(v == p)
 70             continue;
 71         dfs1(v , u , d + 1);
 72         if(size[v] >= size[son[u]])
 73             son[u] = v;
 74         size[u] += size[v];
 75     }
 76 }
 77 
 78 void dfs2(int u , int p , int t) {
 79     top[u] = t , id[u] = ++cnt;
 80     if(son[u] != u)
 81         dfs2(son[u] , u , t);
 82     for(int i = head[u] ; ~i ; i = edge[i].next) {
 83         int v = edge[i].to;
 84         if(v == son[u] || v == p)
 85             continue;
 86         dfs2(v , u , v);
 87     }
 88 }
 89 
 90 struct SegTree {
 91     int l , r;
 92     LL Max;
 93 }T[MAXN << 2];
 94 
 95 void build(int p , int l , int r) {
 96     int mid = (l + r) >> 1;
 97     T[p].l = l , T[p].r = r;
 98     if(l == r) {
 99         return ;
100     }
101     build(p << 1 , l , mid);
102     build((p << 1)|1 , mid + 1 , r);
103 }
104 
105 void updata(int p , int pos , LL num) {
106     int mid = (T[p].l + T[p].r) >> 1;
107     if(T[p].l == T[p].r && T[p].l == pos) {
108         T[p].Max = num;
109         return ;
110     }
111     if(pos <= mid) {
112         updata(p << 1 , pos , num);
113     }
114     else {
115         updata((p << 1)|1 , pos , num);
116     }
117     T[p].Max = max(T[p << 1].Max , T[(p << 1)|1].Max);
118 }
119 
120 LL query(int p , int l , int r) {
121     int mid = (T[p].l + T[p].r) >> 1;
122     if(T[p].l == l && T[p].r == r) {
123         return T[p].Max;
124     }
125     if(r <= mid) {
126         return query(p << 1 , l , r);
127     }
128     else if(l > mid) {
129         return query((p << 1)|1 , l , r);
130     }
131     else {
132         return max(query(p << 1 , l , mid) , query((p << 1)|1 , mid + 1 , r));
133     }
134 }
135 
136 LL find_max(int u , int v) {
137     int fu = top[u] , fv = top[v];
138     LL Max = 0;
139     while(fv != fu) {
140         if(dep[fu] >= dep[fv]) {
141             Max = max(Max , query(1 , id[fu] , id[u]));
142             u = par[fu];
143             fu = top[u];
144         }
145         else {
146             Max = max(Max , query(1 , id[fv] , id[v]));
147             v = par[fv];
148             fv = top[v];
149         }
150     }
151     if(u == v)
152         return Max;
153     else if(dep[u] > dep[v])
154         return max(Max , query(1 , id[son[v]] , id[u]));
155     else
156         return max(Max , query(1 , id[son[u]] , id[v]));
157 }
158 
159 int main()
160 {
161     int n , m;
162     scanf("%d %d" , &n , &m);
163     if(m == 0) {
164         printf("");
165         return 0;
166     }
167     init(n);
168     for(int i = 1 ; i <= m ; ++i) {
169         scanf("%d %d %lld" , &a[i].from , &a[i].to , &a[i].cost);
170         a[i].index = i;
171     }
172     sort(a + 1 , a + m + 1);
173     LL mst_len = mst(m);
174     dfs1(1 , 1 , 0);
175     dfs2(1 , 1 , 1);
176     build(1 , 2 , cnt);
177     for(int i = 1 ; i <= n - 1 ; ++i) {
178         if(dep[b[i].from] < dep[b[i].to])
179             swap(b[i].from , b[i].to);
180         updata(1 , id[b[i].from] , b[i].cost);
181     }
182     sort(a + 1 , a + m + 1 , cmp);
183     for(int i = 1 ; i <= m ; ++i) {
184         if(a[i].flag)
185             printf("%lld
" , mst_len);
186         else {
187             LL temp = find_max(a[i].from , a[i].to);
188             printf("%lld
" , mst_len - temp + a[i].cost);
189         }
190     }
191     return 0;
192 }