HDU

题意:给定一个带权边无向基环树，有两种操作，一种是改变某个边的权值，另一种是询问两点间的最短路径。

可以对环进行缩点，以环为根建立一棵新树，并记录与环相连的所有点和环上的哪个点相连，将路径分为环外和环内的两类进行处理。环外的路径可以用树剖+树状数组维护，环内的路径复制一倍，用另一个树状数组维护。

  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
",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
",qry_tree(a,b));
121         }
122     }
123     return 0;
124 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/asdfsag/p/11285599.html