SPOJ QTREE系列
375.QTREE 给你一棵n个点$n-1$条边的树，支持修改一条边的边权、查询两点之间路径上的最大边权。 树链剖分+线段树基础题 code: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int H[10005],X[20005],P[20005],tot, w[20005],E[20005],num[20005]; inline void add(int x,int y,int z,int no){ P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;num[tot]=no; } int mx[10005<<2]; int to[10005],tt,siz[10005],son[10005],top[10005],dep[10005],f[10005],tim; void dfs1(int x,int fa){ siz[x]=1;son[x]=0;top[x]=0; int mx=0; for(int i=H[x];i;i=X[i]){ if(P[i]==fa) continue; f[P[i]]=x; dep[P[i]]=dep[x]+1; w[P[i]]=E[i]; to[num[i]]=P[i]; dfs1(P[i],x); siz[x]+=siz[P[i]]; if(siz[P[i]]>mx){ mx=siz[P[i]]; son[x]=P[i]; } } } void dfs2(int x,int fa){ if(!top[x]) top[x]=x; num[x]=++tim; E[tim]=w[x]; if(son[x])top[son[x]]=top[x],dfs2(son[x],x); for(int i=H[x];i;i=X[i]){ if(P[i]!=son[x]&&P[i]!=fa){ dfs2(P[i],x); } } } int _c,_l,_r; void ask(int o,int l,int r){ if(_l<=l&&r<=_r){ _c=max(mx[o],_c); return ; }else{ int mid=(l+r)>>1; if(_l<=mid) ask(o<<1,l,mid); if(_r>mid) ask(o<<1|1,mid+1,r); } } int ask(int l,int r){ _c=0; _l=l,_r=r; ask(1,1,n); return _c; } int Ask(int a,int b){ int ret=0; while(top[a]!=top[b]){ int x=top[a],y=top[b]; if(dep[x]<dep[y]) swap(x,y),swap(a,b); ret=max(ask(num[x],num[a]),ret); a=f[x]; } if(a!=b){ if(dep[a]>dep[b]) swap(a,b); ret=max(ret,ask(num[a]+1,num[b])); } return ret; } char s[50]; void change(int o,int l,int r,int p,int k){ if(l==r){ mx[o]=k; }else{ int mid=(l+r)>>1; if(p<=mid) change(o<<1,l,mid,p,k); else change(o<<1|1,mid+1,r,p,k); mx[o]=max(mx[o<<1],mx[o<<1|1]); } } void bd(int o,int l,int r){ if(l==r){ mx[o]=E[l]; }else{ int mid=(l+r)>>1; bd(o<<1,l,mid); bd(o<<1|1,mid+1,r); mx[o]=max(mx[o<<1],mx[o<<1|1]); } } int main(){ scanf("%d",&tt); while(tt--){ tim=tot=0; memset(H,0,sizeof H); scanf("%d",&n); for(int i=1,a,b,c;i<n;i++){ scanf("%d%d%d",&a,&b,&c); add(a,b,c,i); add(b,a,c,i); } dep[1]=1; dfs1(1,-1); dfs2(1,-1); bd(1,1,n); int a,b; while(scanf("%s",s),s[0]!='D'){ if(s[0]=='Q'){ scanf("%d%d",&a,&b); printf("%d\n",Ask(a,b)); }else{ scanf("%d%d",&a,&b); change(1,1,n,num[to[a]],b); } } } return 0; } 913.QTREE2 一棵树，两个操作。 1.询问a到b的最短路。 2.询问a到b的最短路上第k个点是啥。 倍增或者树链剖分。 ...