首先嘚瑟一下这场比赛的排名：59
（第一次看到这么多 √ emmmm）
好了进入正文QAQ
...这道题啊，思路很清晰啊。
首先你看到树上路径边权和，然后还带修改，不是显然可以想到 树剖+线段树 维护重链么？
然后你再看啊，这是一个连通图，然后有 n 个点 n 条边，于是很显然会有一个环（然后就构成了一个 仙人掌 ...不过我并不了解仙人掌）
然后你再看！这里只会有一个环，我们假设没有这个环，那么这就是一道 树剖 模板题，那么我们可不可以特殊地，让这个环当根，除这个环以外的其他节点来简单 树剖 呢？
恩，这不是显然么？ 于是我们考虑怎么处理那个简单环...emmmm！考虑暴力维护，考虑暴力维护，那么我们是 O(n) 的，而修改是 O(1) 的。
那么我们处理一下前缀和呢？很遗憾，这样只不过是将两个复杂度反了一下。那么我们考虑用数据结构优化（中和）这个复杂度。
没错，就是树状数组维护前缀和，达到查询和修改都是 O(log n) 的复杂度（并且常数很小），于是这道题成功的包含了 树剖、线段树、树状数组 这三个算法。
咳咳，别着急啊，这不是还没说怎么找环啊。
emmm...相信不用我说，你就一秒想到了 tarjan 。 对啊，显然啊。
然后就有四个算法了。
还有吗？（难道还不够？四个算法除了树状数组好大其他码量大的很啊）
emmm...没了，真没了
你真要说有的话，就是标记环时候要用的深搜了...（其实完全可以 tarjan 的时候把环标记出来的好伐）
然后，然后...上代码（错误示范，但思想正确，什么时候我订正完了再回来填坑吧）
//by Judge#include<iostream>#include<cstring>#include<cstdio>#define ls k<<1#define rs k<<1|1#define mid (l+r>>1)#define ll long longusing namespace std;const int M=1e5+111;inline int read(){ ???int x=0,f=1; char c=getchar(); ???for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; ???for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;}int n,m,pat,cnt,tim,stop;ll t[M<<2],ff[M];int id[M],s[M],in[M],rk[M];int head[M],dfn[M],low[M],stk[M],blg[M];int siz[M],dep[M],f[M],son[M],top[M],val[M];struct Edge{ ???int to,val,next,frm; ???Edge(int to,int val,int next,int frm): to(to),val(val),next(next),frm(frm){} Edge(){}}e[M<<2];inline void add(int u,int v,int c,int w){ ???e[++pat]=Edge(v,c,head[u],w),head[u]=pat; ???e[++pat]=Edge(u,c,head[v],w),head[v]=pat;}#define v e[i].to#define cc e[i].val/* ???????????tarjan缩点 处理环 ?????????*/void tarjan(int u,int fa){ ???dfn[u]=low[u]=++tim,stk[++stop]=u; ???for(int i=head[u];i;i=e[i].next) if(v!=fa){ ???????if(!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]); ???????else low[u]=min(low[u],dfn[v]); ????} ???if(dfn[u]==low[u]){ ???????int j=stk[stop]; ???????if(j==u) --stop,blg[u]=u; return ; ???????do{ j=stk[stop--],id[++cnt]=j,in[j]=j; }while(j!=u); ???????for(j=2;j<=cnt;++j) ???????for(int i=head[id[j]];i;i=e[i].next) ???????????if(blg[v]!=u) add(u,v,cc,e[i].frm),in[v]=j; ???}}void dfss(int u,int fa,int stp){ ???id[stp]=u,cnt=stp,dfn[u]=stp; ???for(int i=head[u];i;i=e[i].next){ ???????if(blg[v]!=blg[u] || v==fa) continue; ???????if(v!=blg[u]) dfss(v,u,stp+1); in[u]=u; ???????top[v]=blg[v],val[v]=cc,s[e[i].frm]=v; break; ???}}/* ???????????????树剖建树 ??????????????*/void dfs1(int u){ ???siz[u]=1, dep[u]=dep[f[u]]+1; ???for(int i=head[u];i;i=e[i].next){ ???????if(blg[v]!=v || v==f[u]) continue; ???????in[u]?in[v]=in[u]:0,f[v]=u,val[v]=cc,dfs1(v); ???????s[e[i].frm]=v,siz[u]+=siz[v],siz[v]>siz[son[u]]?son[u]=v:0; ???}}void dfs2(int u){ ???if(!top[u]) top[u]=u; dfn[u]=++tim,rk[tim]=u; ???if(!son[u]) return; top[son[u]]=top[u],dfs2(son[u]); ???for(int i=head[u];i;i=e[i].next) ???????if(blg[v]==v && v!=f[u] && v!=son[u]) dfs2(v);}#undef v#undef cc/* ???????binary-indexed-tree ????????????*/inline int lowbit(int x){ ???return x&(-x);}inline void add(int x,int y){ ???for(;x<=n;x+=lowbit(x)) ff[x]+y;}inline ll get_pre(int x,int y,int z=cnt){ ???ll r1=0,r2=0; ???for(;x;x-=lowbit(x)) r1-=ff[x]; ???for(;y;y-=lowbit(y)) r1+=ff[y]; ???for(;z;z-=lowbit(z)) r2+=ff[z]; ???return min(r1,r2-r1);}inline void cbuild(){ ???for(int i=1,j;i<=cnt;++i) add(i,val[id[i]]);}inline void change(int x,int y){ ???add(x,-val[id[x]]),val[id[x]]=y,add(x,val[id[x]]);}/* ?????????segment-tree ????????????????*/void build(int k,int l,int r){ ???if(l==r) return (void)(t[k]=val[rk[l]]); ???build(ls,l,mid), build(rs,mid+1,r), t[k]=t[ls]+t[rs];}void update(int k,int l,int r,int x,int y){ ???if(l>x || r<x) return ; if(l==r) return (void)(t[k]=y); ???update(ls,l,mid,x,y),update(rs,mid+1,r,x,y),t[k]=t[ls]+t[rs];}ll query(int k,int l,int r,int L,int R){ ???if(L>r || l>R) return 0; if(L<=l && r<=R) return t[k]; ???return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R); }/* ???????????树剖询问 ????????????????*/inline ll get_sum(int u,int v){ ???ll ans=0,inu=in[u],inv=in[v]; u=blg[u],v=blg[v]; ???while(top[u]^top[v]){ ???????if(dep[top[u]]<dep[top[v]]) swap(u,v); ???????ans+=query(1,1,tim,dfn[top[u]],dfn[u]),u=f[top[u]]; ???} if(u^v){ ???????if(dep[u]>dep[v]) swap(u,v); ???????ans+=query(1,1,tim,dfn[u]+1,dfn[v]); ???} if(u==id[1]) ans+=get_pre(inu,inv); ???return ans;}int main(){ ???freopen("testdata.in","r",stdin); ????int T=read(),x,y,opt; ???while(T--){ ???????n=read(),m=read(),pat=cnt=tim=0; ???????for(int i=1,u,v,c;i<=n;++i) ???????????in[i]=head[i]=dfn[i]=0, ???????????u=read(),v=read(), ???????????c=read(),add(u,v,c,i); ???????tarjan(1,0), dfss(id[1],0,1); ???????dfs1(id[1]),dfs2(id[1]); ???????cbuild(),build(1,1,tim); ???????while(m--){ ???????????opt=read(),x=read(),y=read(); ???????????if(opt) printf("%lld\n",get_sum(x,y)); ???????????else if(blg[s[x]]!=id[1]) change(dfn[s[x]],y); ???????????else update(1,1,tim,dfn[s[x]],y); ???????} ???}return 0;}顺便推荐一道我刷了 n 多树剖模板题还 debug 了半个小时的题目： 月下“毛景树”，BZOJ 权限题，但洛谷上也有.
这题就是树剖求路径上的边权和，然后带修改（区间修改！两个区间修改！），代码如下，然后有点地方加了解释，其他都不难理解，模板：
//by Judge#include<iostream>#include<cstdio>#define ls k<<1#define rs k<<1|1#define mid (l+r>>1)using namespace std;const int M=1e5+111;const int inf=1e9+7;inline int read(){ ???int x=0,f=1; char c=getchar(); ???for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; ???for(;isdigit(c);c=getchar()) x=x*10+c-'0'; ???return x*f;}inline char cread(){ ???char c=getchar(); while(!islower(c)) c=getchar(); return c;}int n,pat,tim;int head[M],id[M],s[M],t[M<<2],tag[M<<2],ad[M<<2];int siz[M],dep[M],f[M],son[M],dfn[M],top[M],val[M];struct Edge{ ???int to,val,next;}e[M<<1];inline void add(int u,int v,int c){ ???e[++pat]=(Edge){ v,c,head[u] },head[u]=pat; ???e[++pat]=(Edge){ u,c,head[v] },head[v]=pat;}#define v e[i].tovoid dfs1(int u){ ???siz[u]=1; ???for(int i=head[u];i;i=e[i].next){ ???????if(v==f[u]) continue; ???????f[v]=u,dep[v]=dep[u]+1,val[v]=e[i].val; ???????dfs1(v),siz[u]+=siz[v],s[i+1>>1]=v; ???????if(siz[v]>siz[son[u]]) son[u]=v; ????}}void dfs2(int u){ ???dfn[u]=++tim,id[tim]=u; ???if(!top[u]) top[u]=u; if(!son[u]) return ; ???top[son[u]]=top[u],dfs2(son[u]); ???for(int i=head[u];i;i=e[i].next) ???????if(v!=f[u] && v!=son[u]) dfs2(v);}#undef vinline void build(int k,int l,int r){ ???if(l==r) return (void)(t[k]=val[id[l]]); ???build(ls,l,mid),build(rs,mid+1,r),t[k]=max(t[ls],t[rs]);}inline void pushdown(int k){ ??//pushdown 的时候我们考虑两个懒标记在任何时候都只会留下一个，于是判断两下就好了 ????if(tag[k]) t[ls]=t[rs]=tag[ls]=tag[rs]=tag[k],tag[k]=ad[ls]=ad[rs]=0; ???else if(ad[k]){ ???????if(tag[ls]) t[ls]=tag[ls]+=ad[k]; else ad[ls]+=ad[k],t[ls]+=ad[k]; ???????if(tag[rs]) t[rs]=tag[rs]+=ad[k]; else ad[rs]+=ad[k],t[rs]+=ad[k]; ???????ad[k]=0; ???}}void update_to(int k,int l,int r,int L,int R,int x){ ???if(l>R || L>r) return ; if(L<=l && r<=R) return (void)(tag[k]=t[k]=x,ad[k]=0); ?//修改的话，add标记直接作废 ????pushdown(k), update_to(ls,l,mid,L,R,x),update_to(rs,mid+1,r,L,R,x),t[k]=max(t[ls],t[rs]);}void update_add(int k,int l,int r,int L,int R,int x){ ???if(l>R || L>r) return ; if(L<=l && r<=R){ if(tag[k]) t[k]=tag[k]+=x; else ad[k]+=x,t[k]+=x; return ;} ?//区间加的话，根据是否有修改标记来做 ????pushdown(k), update_add(ls,l,mid,L,R,x),update_add(rs,mid+1,r,L,R,x),t[k]=max(t[ls],t[rs]);}int query(int k,int l,int r,int L,int R){ ???if(l>R || L>r) return -inf; if(L<=l && r<=R) return t[k]; ???pushdown(k); return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));}inline void Change(){ ???int x=dfn[s[read()]],w=read(); update_to(1,1,tim,x,x,w);}inline void Cover(){ ???int u=read(),v=read(),w=read(); ???while(top[u]!=top[v]){ ???????if(dep[top[u]]<dep[top[v]]) swap(u,v); ???????update_to(1,1,tim,dfn[top[u]],dfn[u],w),u=f[top[u]]; ???} if(u==v) return ; if(dep[u]>dep[v]) swap(u,v); ???update_to(1,1,tim,dfn[u]+1,dfn[v],w);}inline void Add(){ ???int u=read(),v=read(),w=read(); ???while(top[u]!=top[v]){ ???????if(dep[top[u]]<dep[top[v]]) swap(u,v); ???????update_add(1,1,tim,dfn[top[u]],dfn[u],w),u=f[top[u]]; ???} if(u==v) return ; if(dep[u]>dep[v]) swap(u,v); ???update_add(1,1,tim,dfn[u]+1,dfn[v],w);}inline void Max(){ ???int u=read(),v=read(),res=-inf; ???while(top[u]^top[v]){ ???????if(dep[top[u]]<dep[top[v]]) swap(u,v); ???????res=max(res,query(1,1,tim,dfn[top[u]],dfn[u])),u=f[top[u]]; ???} ???if(u!=v){ ???????if(dep[u]>dep[v]) swap(u,v); ???????res=max(res,query(1,1,tim,dfn[u]+1,dfn[v])); ???} printf("%d\n",res);}int main(){ ???n=read(); int u,v,w,opt; ???for(int i=1;i<n;++i) ???????u=read(),v=read(),w=read(),add(u,v,w); ???dep[1]=1,dfs1(1),dfs2(1),build(1,1,tim); ???while((opt=cread())!='t') ???????switch(opt){ ???????????case 'h': Change(); break; ???????????case 'o': Cover(); break; ???????????case 'd': Add(); break; ???????????case 'a': Max(); break; ???????} return 0;}刷完这两道题...路径边权和什么的（以及一些恶心的线段树双重懒标记题）都不是问题了吧（理论上）
HDU contest808 ?ACM多校第7场 ?Problem - 1008： Traffic Network in Numazu
原文地址：https://www.cnblogs.com/Judge/p/9470522.html