题意:给定一个带权边无向基环树，有两种操作，一种是改变某个边的权值，另一种是询问两点间的最短路径。
可以对环进行缩点，以环为根建立一棵新树，并记录与环相连的所有点和环上的哪个点相连，将路径分为环外和环内的两类进行处理。环外的路径可以用树剖+树状数组维护，环内的路径复制一倍，用另一个树状数组维护。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+10; 5 int hd[N],n,m,ne,sta[N],tp,vis[N],id[N],anc[N],lid[N],nl; 6 int fa[N],son[N],siz[N],dep[N],top[N],bg[N],ed[N],rnk[N],tot; 7 struct E2 {int u,v,c;} e2[N]; 8 struct E {int v,c,nxt;} e[N<<2]; 9 struct BIT { 10 ll c[N<<1]; 11 int n; 12 int lb(int x) {return x&-x;} 13 void add(int u,int x) {for(; u<=n; u+=lb(u))c[u]+=x;} 14 ll get(int u) {ll ret=0; for(; u; u-=lb(u))ret+=c[u]; return ret;} 15 ll sum(int l,int r) {return get(r)-get(l-1);} 16 void init(int _n) {memset(c,0,sizeof c),n=_n;} 17 } tr1,tr2; 18 void addedge(int u,int v,int c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;} 19 bool isloop(int u) {return id[u]==n+1;} 20 bool dfs_loop(int u,int f) { 21 if(vis[u]) { 22 while(!lid[u]) { 23 int v=sta[tp--]; 24 id[v]=n+1,lid[v]=++nl; 25 } 26 return 1; 27 } 28 vis[u]=1,sta[++tp]=u; 29 for(int i=hd[u]; ~i; i=e[i].nxt) { 30 int v=e[i].v; 31 if(v==f)continue; 32 if(dfs_loop(v,u))return 1; 33 } 34 tp--; 35 return 0; 36 } 37 void dfs_anc(int u,int f,int a) { 38 anc[u]=a; 39 for(int i=hd[u]; ~i; i=e[i].nxt) { 40 int v=e[i].v; 41 if(v==f||isloop(v))continue; 42 dfs_anc(v,u,a); 43 } 44 } 45 void dfs_chain_1(int u,int f,int d) { 46 fa[u]=f,son[u]=0,siz[u]=1,dep[u]=d; 47 for(int i=hd[u]; ~i; i=e[i].nxt) { 48 int v=e[i].v; 49 if(v==fa[u]||isloop(v))continue; 50 dfs_chain_1(v,u,d+1),siz[u]+=siz[v]; 51 if(siz[v]>siz[son[u]])son[u]=v; 52 } 53 } 54 void dfs_chain_2(int u,int tp) { 55 top[u]=tp,bg[u]=++tot,rnk[bg[u]]=u; 56 if(son[u])dfs_chain_2(son[u],tp); 57 for(int i=hd[u]; ~i; i=e[i].nxt) { 58 int v=e[i].v; 59 if(v==fa[u]||v==son[u]||isloop(v))continue; 60 dfs_chain_2(v,v); 61 } 62 ed[u]=tot; 63 } 64 void upd(int u,int v,int x) { 65 if(isloop(u)&&isloop(v)) { 66 int l=lid[u],r=lid[v]; 67 if(l>r)swap(l,r); 68 if(r-l!=1)swap(l,r); 69 tr2.add(r,-tr2.sum(r,r)),tr2.add(r+nl,-tr2.sum(r+nl,r+nl)); 70 tr2.add(r,x),tr2.add(r+nl,x); 71 } else { 72 int l=bg[id[u]],r=bg[id[v]]; 73 if(l>r)swap(l,r); 74 tr1.add(r,-tr1.sum(r,r)),tr1.add(r,x); 75 } 76 } 77 ll qry_loop(int u,int v) { 78 int l=lid[u],r=lid[v]; 79 if(l>r)swap(l,r); 80 return min(tr2.sum(l+1,r),tr2.sum(r+1,l+nl)); 81 } 82 ll qry_tree(int u,int v) { 83 int ancu=anc[u],ancv=anc[v]; 84 u=id[u],v=id[v]; 85 ll ret=0; 86 for(; top[u]!=top[v]; u=fa[top[u]]) { 87 if(dep[top[u]]<dep[top[v]])swap(u,v); 88 ret+=tr1.sum(bg[top[u]],bg[u]); 89 } 90 if(dep[u]<dep[v])swap(u,v); 91 ret+=tr1.sum(bg[v]+1,bg[u]); 92 ret+=qry_loop(ancu,ancv); 93 return ret; 94 } 95 int main() { 96 int T; 97 for(scanf("%d",&T); T--;) { 98 memset(hd,-1,sizeof hd),ne=tp=nl=tot=0; 99 memset(vis,0,sizeof vis); 100 scanf("%d%d",&n,&m); 101 for(int i=1; i<=n; ++i) { 102 int u,v,c; 103 scanf("%d%d%d",&u,&v,&c); 104 addedge(u,v,c),addedge(v,u,c); 105 e2[i]= {u,v,c}; 106 } 107 for(int i=1; i<=n; ++i)id[i]=i; 108 dfs_loop(1,0),id[n+1]=n+1; 109 for(int u=1; u<=n; ++u)if(isloop(u))dfs_anc(u,0,u); 110 for(int u=1; u<=n; ++u)if(isloop(u)) { 111 for(int i=hd[u]; ~i; i=e[i].nxt) { 112 int v=e[i].v; 113 if(!isloop(v))addedge(n+1,v,e[i].c); 114 } 115 } 116 dfs_chain_1(n+1,0,1),dfs_chain_2(n+1,n+1); 117 tr1.init(tot),tr2.init(nl*2); 118 for(int i=1; i<=n; ++i)upd(e2[i].u,e2[i].v,e2[i].c); 119 while(m--) { 120 int f,a,b; 121 scanf("%d%d%d",&f,&a,&b); 122 if(f==0)upd(e2[a].u,e2[a].v,b); 123 else printf("%lld\n",qry_tree(a,b)); 124 } 125 } 126 return 0; 127 }
也可以LCA+差分维护每个点到根节点的距离，复杂度少了个log(但实际速度差不了多少)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+10; 5 int hd[N],n,m,ne,sta[N],tp,vis[N],id[N],anc[N],lid[N],nl; 6 int fa[N],son[N],siz[N],dep[N],top[N],bg[N],ed[N],rnk[N],tot; 7 struct E2 {int u,v,c;} e2[N]; 8 struct E {int v,c,nxt;} e[N<<2]; 9 struct BIT { 10 ll c[N<<1]; 11 int n; 12 int lb(int x) {return x&-x;} 13 void add(int u,int x) {for(; u<=n; u+=lb(u))c[u]+=x;} 14 ll get(int u) {ll ret=0; for(; u; u-=lb(u))ret+=c[u]; return ret;} 15 ll sum(int l,int r) {return get(r)-get(l-1);} 16 void init(int _n) {memset(c,0,sizeof c),n=_n;} 17 } tr1,tr2; 18 void addedge(int u,int v,int c) {e[ne]= {v,c,hd[u]},hd[u]=ne++;} 19 bool isloop(int u) {return id[u]==n+1;} 20 bool dfs_loop(int u,int f) { 21 if(vis[u]) { 22 while(!lid[u]) { 23 int v=sta[tp--]; 24 id[v]=n+1,lid[v]=++nl; 25 } 26 return 1; 27 } 28 vis[u]=1,sta[++tp]=u; 29 for(int i=hd[u]; ~i; i=e[i].nxt) { 30 int v=e[i].v; 31 if(v==f)continue; 32 if(dfs_loop(v,u))return 1; 33 } 34 tp--; 35 return 0; 36 } 37 void dfs_anc(int u,int f,int a) { 38 anc[u]=a; 39 for(int i=hd[u]; ~i; i=e[i].nxt) { 40 int v=e[i].v; 41 if(v==f||isloop(v))continue; 42 dfs_anc(v,u,a); 43 } 44 } 45 void dfs_chain_1(int u,int f,int d) { 46 fa[u]=f,son[u]=0,siz[u]=1,dep[u]=d; 47 for(int i=hd[u]; ~i; i=e[i].nxt) { 48 int v=e[i].v; 49 if(v==fa[u]||isloop(v))continue; 50 dfs_chain_1(v,u,d+1),siz[u]+=siz[v]; 51 if(siz[v]>siz[son[u]])son[u]=v; 52 } 53 } 54 void dfs_chain_2(int u,int tp) { 55 top[u]=tp,bg[u]=++tot,rnk[bg[u]]=u; 56 if(son[u])dfs_chain_2(son[u],tp); 57 for(int i=hd[u]; ~i; i=e[i].nxt) { 58 int v=e[i].v; 59 if(v==fa[u]||v==son[u]||isloop(v))continue; 60 dfs_chain_2(v,v); 61 } 62 ed[u]=tot; 63 } 64 void upd(int u,int v,int x) { 65 if(isloop(u)&&isloop(v)) { 66 int l=lid[u],r=lid[v]; 67 if(l>r)swap(l,r); 68 if(r-l!=1)swap(l,r); 69 tr2.add(r,x),tr2.add(r+nl,x); 70 } else { 71 u=id[u],v=id[v]; 72 if(fa[u]==v)swap(u,v); 73 tr1.add(bg[v],x),tr1.add(ed[v]+1,-x); 74 } 75 } 76 ll qry_loop(int u,int v) { 77 int l=lid[u],r=lid[v]; 78 if(l>r)swap(l,r); 79 return min(tr2.sum(l+1,r),tr2.sum(r+1,l+nl)); 80 } 81 ll qry_tree(int u,int v) { 82 int ancu=anc[u],ancv=anc[v]; 83 u=id[u],v=id[v]; 84 ll ret=tr1.get(bg[u])+tr1.get(bg[v]); 85 for(; top[u]!=top[v]; u=fa[top[u]]) 86 if(dep[top[u]]<dep[top[v]])swap(u,v); 87 if(dep[u]<dep[v])swap(u,v); 88 ret-=2*tr1.get(bg[v]); 89 ret+=qry_loop(ancu,ancv); 90 return ret; 91 } 92 int main() { 93 int T; 94 for(scanf("%d",&T); T--;) { 95 memset(hd,-1,sizeof hd),ne=tp=nl=tot=0; 96 memset(vis,0,sizeof vis); 97 scanf("%d%d",&n,&m); 98 for(int i=1; i<=n; ++i) { 99 int u,v,c; 100 scanf("%d%d%d",&u,&v,&c); 101 addedge(u,v,c),addedge(v,u,c); 102 e2[i]= {u,v,c}; 103 } 104 for(int i=1; i<=n; ++i)id[i]=i; 105 dfs_loop(1,0),id[n+1]=n+1; 106 for(int u=1; u<=n; ++u)if(isloop(u))dfs_anc(u,0,u); 107 for(int u=1; u<=n; ++u)if(isloop(u)) { 108 for(int i=hd[u]; ~i; i=e[i].nxt) { 109 int v=e[i].v; 110 if(!isloop(v))addedge(n+1,v,e[i].c); 111 } 112 } 113 dfs_chain_1(n+1,0,1),dfs_chain_2(n+1,n+1); 114 tr1.init(tot),tr2.init(nl*2); 115 for(int i=1; i<=n; ++i)upd(e2[i].u,e2[i].v,e2[i].c); 116 while(m--) { 117 int f,a,b; 118 scanf("%d%d%d",&f,&a,&b); 119 if(f==0)upd(e2[a].u,e2[a].v,b-e2[a].c),e2[a].c=b; 120 else printf("%lld\n",qry_tree(a,b)); 121 } 122 } 123 return 0; 124 }
HDU - 6393 Traffic Network in Numazu (基环树+树链剖分/LCA)
原文：https://www.cnblogs.com/asdfsag/p/11285599.html