题解
先构建出最小生成树，如果删的是非树边，直接输出答案
否则问题转化为，把该边删掉后剩下两个联通块，两个端点分别在两个块内的最小边权，LCT可以维护
不妨换一种思考方向：考虑一条非树边可以代替哪些树边，根据次小生成树的套路，它可以代替树上两端点之间路径上的任意一条边
因此，对MST进行树链剖分，然后对每一条非树边更新它两端点之间路径的最小值即可
注意：题目给的图可能不连通，需要特判！
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline char smax(T&x,const U&y){return x<y?x=y,1:0;}
namespace IOManager{
const unsigned int iSize(131072),oSize(65536);
char buf[iSize],wbuf[oSize+128],*iT=buf+iSize,*iS=iT-1,*oS=wbuf-1,*oT=wbuf+oSize;
struct FastIO{
inline char gc(){
if(++iS==iT)fread(iS=buf,1,iSize,stdin);return *iS;
}
template<typename T>
inline void read(T&w){register char c,p=0;
while(isspace(c=gc()));if(c=='-')p=1,c=gc();w=c^48u;
while(isdigit(c=gc()))w=w*10+(c^48u);if(p)w=-w;
}
inline int read(){register int x;return read(x),x;}
inline void flush(){fwrite(wbuf,1,oS-wbuf+1,stdout);oS=wbuf-1;}
~FastIO(){flush();}
inline FastIO&operator<<(const char&c){if(oS>oT)flush();*++oS=c;}
inline void putstr(const string&s){
const int l=s.length();
if(oS>oT)flush();
for(int i=0;i<l;++i)*++oS=s[i];
}
template<typename T>
inline FastIO&operator<<(T x){
static char stk[30];int top=0;
if(oS>oT)flush();
if(x==0)return *++oS='0',*this;
if(x<0)x=-x,*++oS='-';
for(;x;x/=10)stk[++top]=x%10^48;
while(top)*++oS=stk[top--];
return*this;
}
};
}IOManager::FastIO io;
#define read io.read
const int N=50005;
int n,m,tot,head[N],vis[N<<1],to[N<<1],nxt[N<<1],top[N],siz[N],in[N],son[N],dep[N],fa[N],cnt;
struct edge{int u,v,w,id;}a[N<<1],b[N<<1];
inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x];head[x]=tot;}
#define y to[i]
inline void go1(int x){
siz[x]=1;
for(int i=head[x];i;i=nxt[i])if(y!=fa[x])
fa[y]=x,dep[y]=dep[x]+1,go1(y),siz[x]+=siz[y],siz[y]>siz[son[x]]&&(son[x]=y);
}
inline void go2(int x,int anc){
in[x]=++cnt,top[x]=anc;
if(!son[x])return;go2(son[x],anc);
for(int i=head[x];i;i=nxt[i])if(y!=fa[x]&&y!=son[x])go2(y,y);
}
#undef y
inline bool cmp(edge x,edge y){return x.w<y.w;}
int pa[N];
inline int find(int x){return pa[x]?pa[x]=find(pa[x]):x;}
int tag[N<<2];
#define ls o<<1
#define rs o<<1|1
inline void update(int o,int l,int r,int x,int y,int z){
if(z>tag[o])return;
if(x<=l&&r<=y)return (void)(tag[o]=z);
int mid=l+r>>1;
if(x<=mid)update(ls,l,mid,x,y,z);
if(y>mid)update(rs,mid+1,r,x,y,z);
}
inline int ask(int o,int l,int r,int x){
int ans=tag[0];
while(1){
smin(ans,tag[o]);
if(l==r)return ans;
int mid=l+r>>1;
x<=mid?(o=ls,r=mid):(o=rs,l=mid+1);
}
return -1;
}
inline void update(int x,int y,int z){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,in[top[x]],in[x],z);x=fa[top[x]];
}
if(x==y)return;
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,in[x]+1,in[y],z);
}
int main(){
n=read(),m=read();
REP(i,1,m)a[i]=b[i]=(edge){read(),read(),read(),i};
sort(a+1,a+1+m,cmp);
int ans=0;
REP(i,1,m){
int x=find(a[i].u),y=find(a[i].v);
if(x!=y)
add(a[i].u,a[i].v),add(a[i].v,a[i].u),
pa[x]=y,vis[a[i].id]=1,ans+=a[i].w;
}
go1(1),go2(1,1);
if(siz[1]<n){
int Q=read();
while(Q--)io.putstr("Not connected
");
return 0;
}
memset(tag,0x3f,sizeof tag);
REP(i,1,m)if(!vis[i])update(b[i].u,b[i].v,b[i].w);
int Q=read();
while(Q--){
int id=read();
if(!vis[id])io<<ans<<'
';
else{
int&x=b[id].u,&y=b[id].v;
if(dep[x]<dep[y])swap(x,y);
int r=ask(1,1,n,in[x]);
if(r==tag[0])io.putstr("Not connected
");
else io<<ans-b[id].w+r<<'
';
}
}
return 0;
}
UPD.20181107
根据BZOJ2054疯狂的馒头的思想，这题可以用并查集优化，思路与上文相同
复杂度 (O(alpha(n) imes n))
代码没时间写了，就咕了吧。。