OJ题号：
BZOJ1977、COGS2453
题目大意：
给你一个无向连通图，求严格次小生成树。
思路：
对于一般次小生成树，我们有一个结论：一般次小生成树一定可以通过替换掉最小生成树某一条边得到。
因此对于一般次小生成树，我们只需要枚举不在MST上的每一条边，并枚举这条边对应两点路径上的所有边，尝试交换这两条边即可。
显然枚举树上每一条边的复杂度是O(n)的，会TLE，因此我们可以用树剖或者树上倍增的方法记录区间最大边。
然而这题要求的是严格次小生成树，所以万一你枚举的这两条边相等就WA了。
为了保险起见，我们再记录区间最大边的同时，还要记录区间严格次大边。
然后枚举的时候只要判断当前区间最大边是否和那条非树边相等，如果相等的话就取那条次大边即可。
一开始因为没有权限号就去COGS上交，然后随随便便就A了，还跑了Rank1。
但是据说那里数据比较水，就找q234rty借了权限号，去BZOJ上交，果然WA了。
随机了一个小数据，发现是最后倍增求最大树边的时候最后一层没跳上去。
去网上拉了一个程序对拍，发现无限WA。
拿了一个数据手动模拟了一遍，发现原来是网上的题解错了。。
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const long long inf=0x7fffffffffffffffll;
const int V=,logV=;
inline int log2(const float x) {
return ((unsigned&)x>>&)-;
}
class DisjointSet {
private:
int anc[V];
int Find(const int &x) {
return x==anc[x]?x:anc[x]=Find(anc[x]);
}
public:
DisjointSet() {
for(register int i=;i<V;i++) {
anc[i]=i;
}
}
void Union(const int &x,const int &y) {
anc[Find(x)]=Find(y);
}
bool isConnected(const int &x,const int &y) {
return Find(x)==Find(y);
}
};
DisjointSet s;
struct Edge1 {
int u,v,w;
bool inMST;
bool operator < (const Edge1 &another) const {
return w<another.w;
}
};
std::vector<Edge1> e1;
struct Edge {
int to,w;
};
std::vector<Edge> e[V];
inline void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
}
long long mst=;
inline void kruskal() {
std::sort(e1.begin(),e1.end());
for(register unsigned i=;i<e1.size();i++) {
const int &u=e1[i].u,&v=e1[i].v,&w=e1[i].w;
if(s.isConnected(u,v)) continue;
s.Union(u,v);
add_edge(u,v,w);
add_edge(v,u,w);
e1[i].inMST=true;
mst+=w;
}
}
int anc[V][logV],max[V][logV],max2[V][logV];
int dep[V];
std::queue<int> q;
inline void bfs() {
q.push();
while(!q.empty()) {
const int x=q.front();
q.pop();
dep[x]=dep[anc[x][]]+;
for(register int i=;i<=log2(dep[x]);i++) {
anc[x][i]=anc[anc[x][i-]][i-];
max[x][i]=std::max(max[x][i-],max[anc[x][i-]][i-]);
if(max[x][i-]!=max[anc[x][i-]][i-]) {
max2[x][i]=std::min(max[x][i-],max[anc[x][i-]][i-]);
} else {
max2[x][i]=std::max(max2[x][i-],max2[anc[x][i-]][i-]);
}
}
for(register unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
if(y==anc[x][]) continue;
anc[y][]=x;
max[y][]=e[x][i].w;
q.push(y);
}
}
}
inline int maxEdge(int x,int y,const int &w) {
int tmax=;
while(dep[x]!=dep[y]) {
if(dep[x]<dep[y]) std::swap(x,y);
for(register int i=log2(dep[x]);i>=;i--) {
if(dep[anc[x][i]]>=dep[y]) {
if(max[x][i]<w) {
tmax=std::max(tmax,max[x][i]);
} else if(max2[x][i]<w) {
tmax=std::max(tmax,max2[x][i]);
}
x=anc[x][i];
}
}
}
if(x==y) return tmax;
for(register int i=log2(dep[x]);i>=;i--) {
if(anc[x][i]!=anc[y][i]) {
if(max[x][i]<w) {
tmax=std::max(tmax,max[x][i]);
} else if(max2[x][i]<w) {
tmax=std::max(tmax,max2[x][i]);
}
if(max[y][i]<w) {
tmax=std::max(tmax,max[y][i]);
} else if(max2[y][i]<w) {
tmax=std::max(tmax,max2[y][i]);
}
x=anc[x][i],y=anc[y][i];
}
}
if(max[x][]<w) {
tmax=std::max(tmax,max[x][]);
} else if(max2[x][]<w) {
tmax=std::max(tmax,max2[x][]);
}
if(max[y][]<w) {
tmax=std::max(tmax,max[y][]);
} else if(max2[y][]<w) {
tmax=std::max(tmax,max2[y][]);
}
return tmax;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("secmst.in","r+",stdin);
freopen("secmst.out","w+",stdout);
#endif
int n=getint(),m=getint();
for(register int i=;i<=m;i++) {
const int u=getint(),v=getint(),w=getint();
e1.push_back((Edge1){u,v,w,false});
}
kruskal();
bfs();
long long ans=inf;
for(register unsigned i=;i<e1.size();i++) {
if(e1[i].inMST) continue;
const int &u=e1[i].u,&v=e1[i].v,&w=e1[i].w;
ans=std::min(ans,mst-maxEdge(u,v,w)+w);
}
printf("%lld\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin),fclose(stdout);
#endif
return ;
}