题面：https://www.lydsy.com/JudgeOnline/problem.php?id=2238
思路：先求个最小生成树，然后就对最小生成树上的边做树剖，依次对非树边进行处理，维护非树边两端连成的路径的最小值（用非树边的权值维护），然后对于每个询问，求出覆盖在那条线段上的最小值，用real_sum（最小生成树的边权和）去加加减减就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=,maxm=,maxw=,inf=<<;
int N,M,x,y,w,Q,edge_head[maxn],num_edge=,edge_head2[maxn],num_edge2=,fa[maxn],real_sum=;
int size[maxn],son[maxn],seg[maxn],rev[maxn],f[maxn],dep[maxn],top[maxn],X,Y,_ans,T;
bool via[maxm],ans=;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
struct Edge{
int to,dis,nx,from;
}edge[maxm<<];
struct Edge2{
int to,dis,nx,from,id;
}edge2[maxm];
inline void Add_edge(int from,int to,int dis){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].from=from;
edge[num_edge].to=to;
edge[num_edge].dis=dis;
edge_head[from]=num_edge;
return;
}
inline void Add_edge2(int from,int to,int dis){
edge2[++num_edge2].nx=edge_head2[from];
edge2[num_edge2].from=from;
edge2[num_edge2].to=to;
edge2[num_edge2].dis=dis;
edge2[num_edge2].id=num_edge2;
edge_head2[from]=num_edge2;
return;
}
inline bool cmp(const Edge2&a,const Edge2&b){
if(a.dis<b.dis)return ;
return ;
}
inline int getf(int x){
if(fa[x]==x)return x;
fa[x]=getf(fa[x]);
return fa[x];
}
void Kruskal(){
sort(edge2+,edge2+num_edge2+,cmp);
for(int i=;i<=N;i++)fa[i]=i;
int num=;
for(int i=;i<=num_edge2;i++){
int x=edge2[i].from,y=edge2[i].to;
int fx=getf(x),fy=getf(y);
if(fx!=fy){
num++;
fa[fx]=fy;
via[edge2[i].id]=;
real_sum+=edge2[i].dis;
if(num==N-)break;
}
}
if(num!=N-)ans=;
return;
}
inline void Dfs1(int x,int _f){
f[x]=_f;
size[x]=;
dep[x]=dep[_f]+;
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
if(y!=_f&&((((i&)==)&&via[(i>>)+])||(((i&)==)&&via[i>>]))){
Dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
return;
}
inline void Dfs2(int x){
if(son[x]){
int y=son[x];
top[y]=top[x];
seg[y]=++seg[];
rev[seg[]]=y;
Dfs2(y);
}
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
if(top[y]==&&((((i&)==)&&via[(i>>)+])||(((i&)==)&&via[i>>]))){
top[y]=y;
seg[y]=++seg[];
rev[seg[]]=y;
Dfs2(y);
}
}
return;
}
struct Tree{
int l,r,mina,lazy;
}t[maxn<<];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;t[x].mina=inf;t[x].lazy=inf;
if(l==r)return;
int ls=x<<,rs=x<<|,mid=(l+r)>>;
Build(ls,l,mid);Build(rs,mid+,r);
return;
}
inline void Pushdown(int x){
int ls=x<<,rs=x<<|,lazy=t[x].lazy;
if(lazy!=inf){
t[ls].mina=min(t[ls].mina,lazy);t[rs].mina=min(t[rs].mina,lazy);
t[ls].lazy=min(t[ls].lazy,lazy);t[rs].lazy=min(t[rs].lazy,lazy);
t[x].lazy=inf;
}
return;
}
inline void Update(int x,int ql,int qr,int e){
int l=t[x].l,r=t[x].r;
if(ql<=l&&r<=qr){
t[x].mina=min(t[x].mina,e);
t[x].lazy=min(t[x].lazy,e);
return;
}
int ls=x<<,rs=x<<|,mid=(l+r)>>;
Pushdown(x);
if(ql<=mid)Update(ls,ql,qr,e);
if(qr>mid)Update(rs,ql,qr,e);
return;
}
inline void Query(int x,int q){
int l=t[x].l,r=t[x].r;
if(q==l&&l==r){
_ans=min(_ans,t[x].mina);
return;
}
int mid=(l+r)>>,ls=x<<,rs=x<<|;
Pushdown(x);
if(q<=mid)Query(ls,q);
else Query(rs,q);
return;
}
inline void Work(int x,int y,int dis){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
Update(,seg[fx],seg[x],dis);
x=f[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
if(x==y)return;
Update(,seg[x]+,seg[y],dis);
return;
}
int main(){
N=rd();M=rd();
for(int i=;i<=M;i++){
x=rd();y=rd();w=rd();
Add_edge2(x,y,w);
Add_edge(x,y,w);
Add_edge(y,x,w);
}
Kruskal();
scanf("%d",&Q);
Dfs1(,);
seg[]=seg[]=rev[]=top[]=;
Dfs2();
Build(,,seg[]);
for(int i=;i<=M;i++)if(via[i]==)Work(edge[i<<].from,edge[i<<].to,edge[i<<].dis);
while(Q--){
scanf("%d",&T);
if(ans==){
puts("Not connected");
continue;
}
if(via[T]==)printf("%d\n",real_sum);
else{
X=edge[T<<].from,Y=edge[T<<].to;_ans=inf;
if(dep[X]>dep[Y])Query(,seg[X]);else Query(,seg[Y]);
if(_ans==inf){
puts("Not connected");
continue;
}
_ans=real_sum-edge[T<<].dis+_ans;
printf("%d\n",_ans);
}
}
return ;
}
后记：“&”的优先级小于“==”的优先级；线段树查询时要注意ql不能大于qr；边权下移后处理点权时要小心；什么情况要pushdown、pushup要考虑清楚；我的线段树真菜