III.QSUM u v ：询问从点 u 到点 v 的路径上的节点的权值和。
注意：从点 u 到点 v 的路径上的节点包括 u 和 v 本身。
题解：用树剖瞎搞搞
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cctype> #include<iomanip> using namespace std; inline int read(){ int i=0,f=1; char ch; for(ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) i=(i<<1)+(i<<3)+(ch^48); return i*f; } int buf[1024]; inline void write(int x){ if(!x){putchar('0');return ;} if(x<0){putchar('-');x=-x;} while(x){buf[++buf[0]]=x,x/=10;} while(buf[0]) putchar(buf[buf[0]--]+48); return ; } #define stan 33333 int tot,nxt[stan*2],first[stan],goal[stan*2]; int dep[stan],sze[stan],pos[stan],idx[stan],fa[stan],son[stan],top[stan],now; int sum[stan*4],maxn[stan*4]; int n,a,b,u,v,t,val[stan],q; char quest[10]; void addedge(int a,int b){ ++tot;nxt[tot]=first[a];first[a]=tot;goal[tot]=b; ++tot;nxt[tot]=first[b];first[b]=tot;goal[tot]=a; return ; } void preact(){ static int que[90909];int q=1; que[q]=1;dep[1]=1; for(int i=1;i<=q;++i){ int u=que[i]; sze[u]=1; for(int p=first[u];p;p=nxt[p]) if(goal[p]!=fa[u]){ fa[goal[p]]=u; que[++q]=goal[p]; dep[goal[p]]=dep[u]+1; } } for(int i=q;i>=2;--i){ int u=que[i]; sze[fa[u]]+=sze[u]; if(sze[u]>sze[son[fa[u]]]) son[fa[u]]=u; } for(int i=1;i<=n;++i){ int u=que[i]; if(top[u]) continue; for(int v=u;v;v=son[v]){ pos[v]=++now; idx[now]=v; top[v]=u; } } } void build(int pos,int l,int r){ if(l==r){ sum[pos]=val[idx[l]]; maxn[pos]=val[idx[l]]; return ; } int mid=l+r>>1; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; maxn[pos]=max(maxn[pos<<1],maxn[pos<<1|1]); return ; } void insert(int pos,int l,int r,int p,int t){ if(l==r){ sum[pos]=t; maxn[pos]=t; return ; } int mid=l+r>>1; if(p<=mid) insert(pos<<1,l,mid,p,t); else insert(pos<<1|1,mid+1,r,p,t); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; maxn[pos]=max(maxn[pos<<1],maxn[pos<<1|1]); return ; } int querysum(int pos,int l,int r,int x,int y){ if(x<=l&&r<=y) return sum[pos]; int mid=l+r>>1; int ret=0; if(x<=mid) ret+=querysum(pos<<1,l,mid,x,y); if(y>mid) ret+=querysum(pos<<1|1,mid+1,r,x,y); return ret; } int querymax(int pos,int l,int r,int x,int y){ if(x<=l&&r<=y) return maxn[pos]; int mid=l+r>>1; int ret=-999999999; if(x<=mid) ret=max(ret,querymax(pos<<1,l,mid,x,y)); if(y>mid) ret=max(ret,querymax(pos<<1|1,mid+1,r,x,y)); return ret; } int pathsum(int u,int v){ int ret=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ret+=querysum(1,1,n,pos[top[u]],pos[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); ret+=querysum(1,1,n,pos[u],pos[v]); return ret; } int pathmax(int u,int v){ int ret=-999999999; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ret=max(ret,querymax(1,1,n,pos[top[u]],pos[u])); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); ret=max(ret,querymax(1,1,n,pos[u],pos[v])); return ret; } signed main(){ n=read(); for(int i=1;i<n;++i){ a=read();b=read(); addedge(a,b); } for(int i=1;i<=n;++i) val[i]=read(); preact(); build(1,1,n); q=read(); for(int i=1;i<=q;++i){ scanf("%s",quest); if(quest[0]=='C'){ u=read();t=read(); insert(1,1,n,pos[u],t); }else{ u=read();v=read(); if(quest[1]=='S'){ write(pathsum(u,v)); puts(" "); }else{ write(pathmax(u,v)); puts(" "); } } } return 0; } 树剖变式：边剖
描述：输入文件的第一行有一个整数N，代表矿的数量。矿的编号是1到N。
接下来N-1行每行有三个整数a,b,c，代表第i号矿和第j号矿之间有一条路，在初始时这条路的困难值为c。
接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值修改为ti，后者代表查询a到b所经过的道路中的最大困难值。
输入数据以一行“DONE”结束。
题解：改边为点，边权存于子节点，除去lca即可。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cctype> #include<iomanip> using namespace std; inline int read(){ int i=0,f=1; char ch; for(ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) i=(i<<1)+(i<<3)+(ch^48); return i*f; } int buf[1024]; inline void write(int x){ if(!x){putchar('0');return ;} if(x<0){putchar('-');x=-x;} while(x){buf[++buf[0]]=x,x/=10;} while(buf[0]) putchar(buf[buf[0]--]+48); return ; } #define stan 33333 int tot,nxt[stan*2],first[stan],goal[stan*2],dis[stan*2],exi[stan*2],to[stan]; int dep[stan],sze[stan],pos[stan],idx[stan],fa[stan],son[stan],top[stan],now; int sum[stan*4],maxn[stan*4]; int n,a,b,c,u,v,t,val[stan],q; char quest[10]; void addedge(int a,int b,int c,int d){ ++tot;nxt[tot]=first[a];first[a]=tot;goal[tot]=b;dis[tot]=c;exi[tot]=d; ++tot;nxt[tot]=first[b];first[b]=tot;goal[tot]=a;dis[tot]=c;exi[tot]=d; return ; } void preact(){ static int que[90909];int q=1; que[q]=1;dep[1]=1; for(int i=1;i<=q;++i){ int u=que[i]; sze[u]=1; for(int p=first[u];p;p=nxt[p]) if(goal[p]!=fa[u]){ fa[goal[p]]=u; que[++q]=goal[p]; dep[goal[p]]=dep[u]+1; val[goal[p]]=dis[p]; to[exi[p]]=goal[p]; } } for(int i=q;i>=2;--i){ int u=que[i]; sze[fa[u]]+=sze[u]; if(sze[u]>sze[son[fa[u]]]) son[fa[u]]=u; } for(int i=1;i<=n;++i){ int u=que[i]; if(top[u]) continue; for(int v=u;v;v=son[v]){ pos[v]=++now; idx[now]=v; top[v]=u; } } } void build(int pos,int l,int r){ if(l==r){ sum[pos]=val[idx[l]]; maxn[pos]=val[idx[l]]; return ; } int mid=l+r>>1; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; maxn[pos]=max(maxn[pos<<1],maxn[pos<<1|1]); return ; } void insert(int pos,int l,int r,int p,int t){ if(l==r){ sum[pos]=t; maxn[pos]=t; return ; } int mid=l+r>>1; if(p<=mid) insert(pos<<1,l,mid,p,t); else insert(pos<<1|1,mid+1,r,p,t); sum[pos]=sum[pos<<1]+sum[pos<<1|1]; maxn[pos]=max(maxn[pos<<1],maxn[pos<<1|1]); return ; } int querysum(int pos,int l,int r,int x,int y){ if(x>y) return 0; if(x<=l&&r<=y) return sum[pos]; int mid=l+r>>1; int ret=0; if(x<=mid) ret+=querysum(pos<<1,l,mid,x,y); if(y>mid) ret+=querysum(pos<<1|1,mid+1,r,x,y); return ret; } int querymax(int pos,int l,int r,int x,int y){ if(x>y) return -999999999; if(x<=l&&r<=y) return maxn[pos]; int mid=l+r>>1; int ret=-999999999; if(x<=mid) ret=max(ret,querymax(pos<<1,l,mid,x,y)); if(y>mid) ret=max(ret,querymax(pos<<1|1,mid+1,r,x,y)); return ret; } int pathsum(int u,int v){ int ret=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ret+=querysum(1,1,n,pos[top[u]],pos[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); ret+=querysum(1,1,n,pos[u]+1,pos[v]); return ret; } int pathmax(int u,int v){ int ret=-999999999; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ret=max(ret,querymax(1,1,n,pos[top[u]],pos[u])); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); ret=max(ret,querymax(1,1,n,pos[u]+1,pos[v])); return ret; } signed main(){ //freopen("qtree.in","r",stdin); //freopen("qtree.out","w",stdout); n=read(); for(int i=1;i<n;++i){ a=read();b=read();c=read(); addedge(a,b,c,i); } preact(); build(1,1,n); scanf("%s",quest); while(quest[0]!='D'){ if(quest[0]=='C'){ u=read();t=read(); insert(1,1,n,pos[to[u]],t); }else{ u=read();v=read(); write(pathmax(u,v)); puts(" "); } scanf("%s",quest); } return 0; }树剖用途(1)：LCA 描述：只是LCA加上多组询问 题解：需要清空的不只是邻接表，还有son数组 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cctype> #include<iomanip> using namespace std; inline int read(){ int i=0,f=1; char ch; for(ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) i=(i<<1)+(i<<3)+(ch^48); return i*f; } int buf[1024]; inline void write(int x){ if(!x){putchar('0');return ;} if(x<0){putchar('-');x=-x;} while(x){buf[++buf[0]]=x,x/=10;} while(buf[0]) putchar(buf[buf[0]--]+48); return ; } #define stan 10010 int tot,nxt[stan*2],first[stan],goal[stan*2],dis[stan],T,sta; int sze[stan],fa[stan],dep[stan],son[stan],top[stan],que[190909]; int n,a,b,c; void addedge(int a,int b){ ++tot;nxt[tot]=first[a];first[a]=tot;goal[tot]=b; ++tot;nxt[tot]=first[b];first[b]=tot;goal[tot]=a; return ; } void preact(){ int q=1; for(int i=1;i<=n;++i) if(dis[i]==0){ sta=i; break; } que[q]=sta;dep[sta]=1; for(int i=1;i<=q;++i){ int u=que[i]; sze[u]=1; for(int p=first[u];p;p=nxt[p]) if(goal[p]!=fa[u]){ fa[goal[p]]=u; que[++q]=goal[p]; dep[goal[p]]=dep[u]+1; } } for(int i=q;i>=2;--i){ int u=que[i]; sze[fa[u]]+=sze[u]; if(sze[u]>sze[son[fa[u]]]) son[fa[u]]=u; } for(int i=1;i<=n;++i){ int u=que[i]; if(top[u]) continue; for(int v=u;v;v=son[v]) top[v]=u; } } int getans(int x,int y){ int u=x,v=y; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); return u; } signed main(){ T=read(); while(T--){ tot=0; memset(que,0,sizeof(que)); memset(first,0,sizeof(first)); memset(dis,0,sizeof(dis)); memset(son,0,sizeof(son)); memset(top,0,sizeof(top)); n=read(); for(int i=1;i<n;++i){ a=read();b=read(); ++dis[b]; addedge(a,b); } preact(); a=read();b=read(); write(getans(a,b)); puts(" "); } return 0; } 题目来源：树的统计：点击打开链接边剖：点击打开链接
LCA：点击打开链接
