HDU - 6393 Traffic Network in Numazu（树链剖分+基环树）

#include<bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int maxn = 2e5+5;struct side { ???int u,v,w; ???int ne;} s[maxn];struct edge { ???int l,r; ???ll v;} e[maxn<<2];int n,q;int head[maxn],len;int val[maxn],hold[maxn],pre[maxn];int deep[maxn],fa[maxn],ve[maxn],son[maxn],top[maxn],p[maxn],fp[maxn],sz;void add(int u,int v,int w) { ???s[len].u = u; ???s[len].v = v; ???s[len].w = w; ???s[len].ne = head[u]; ???head[u] = len++;}int find(int x) { ???return pre[x] == x?x:pre[x] = find(pre[x]);}void dfs1(int u,int p,int d) { ???deep[u] = d; ???fa[u] = p; ???ve[u] = 1; ???son[u] = -1; ???for(int i = head[u]; i!= -1; i = s[i].ne) { ???????if(s[i].v == p) continue; ???????val[s[i].v] = s[i].w; //把边权值赋给相连的点 ???????hold[i>>1] = s[i].v;//这条边的权值被哪个点掌握着 ???????dfs1(s[i].v,u,d+1); ???????ve[u]+= ve[s[i].v]; ???????if(son[u] == -1||ve[s[i].v]> ve[son[u]]) ???????????son[u] = s[i].v; ???} ???return ;}void dfs2(int u,int sp) { ???top[u] = sp; ???p[u] = ++sz; ???fp[p[u]] = u; ???if(son[u] == -1) return ; ???dfs2(son[u],sp); ???for(int i = head[u]; i!= -1; i = s[i].ne) { ???????if(s[i].v == son[u]||s[i].v == fa[u]) continue; ???????dfs2(s[i].v,s[i].v); ???} ???return ;}void build(int i,int l,int r) { ???e[i].l = l; ???e[i].r = r; ???if(l == r) { ???????e[i].v = val[fp[l]]; ???????return ; ???} ???int mid = (l+r)>>1; ???build(i<<1,l,mid); ???build(i<<1|1,mid+1,r); ???e[i].v = e[i<<1].v+e[i<<1|1].v;}void modify(int i,int pos,int v) { ???if(pos> e[i].r||pos< e[i].l) return ; ???if(e[i].l == e[i].r) { ???????e[i].v = v; ???????return ; ???} ???modify(i<<1,pos,v); ???modify(i<<1|1,pos,v); ???e[i].v = e[i<<1].v+e[i<<1|1].v;}ll query(int i,int l,int r) { ???if(e[i].r< l||e[i].l> r) return 0; ???if(e[i].l>= l&&e[i].r<= r) return e[i].v; ???return query(i<<1,l,r)+query(i<<1|1,l,r);}ll demand(int x,int y) { ???int fx = top[x]; ???int fy = top[y]; ???ll ans = 0; ???while(fx!= fy) { ???????if(deep[fx]< deep[fy]) { ???????????swap(fx,fy); ???????????swap(x,y); ???????} ???????ans+= query(1,p[fx],p[x]); ???????x = fa[fx]; ???????fx = top[x]; ???} ???if(x == y) return ans; ???if(deep[x]> deep[y]) swap(x,y); ???ans+= query(1,p[son[x]],p[y]); ???return ans;}void init() { ???sz = len = 0; ???mem(head,-1); ???for(int i = 0; i<= n; i++) pre[i] = i;}int main() { ???int t; ???cin>>t; ???while(t--) { ???????int su,sv,sc,ss; ???????scanf("%d %d",&n,&q); ???????init(); ???????for(int i = 1; i<= n; i++) { ???????????int u,v,w; ???????????scanf("%d %d %d",&u,&v,&w); ???????????int fx = find(u); ???????????int fy = find(v); ???????????if(fx == fy) { ???????????????len+= 2; ???????????????ss = i; ???????????????su = u; ???????????????sv = v; ???????????????sc = w; ???????????????continue; ???????????} else ???????????????pre[fy] = fx; ???????????add(u,v,w); ???????????add(v,u,w); ???????} ???????dfs1(1,-1,1); ???????dfs2(1,1); ???????build(1,1,n); ???????while(q--) { ???????????int o,x,y; ???????????scanf("%d %d %d",&o,&x,&y); ???????????if(o == 0) { ???????????????x--; ???????????????if(x == ss) { ???????????????????sc = y; ???????????????????continue; ???????????????} ???????????????modify(1,p[hold[x]],y); ???????????} else { ???????????????ll ans; ???????????????ans = sc+min(demand(x,su)+demand(y,sv),demand(x,sv)+demand(y,su)); ???????????????ans = min(ans,demand(x,y)); ???????????????printf("%lld\n",ans); ???????????} ???????} ???} ???return 0;}