Qtree Ⅰ
题意：https://vjudge.net/problem/SPOJ-QTREE
带修路径查询最大边权
sol ：树链剖分，之后每条重链就是一个连续的区间，拿线段树维护即可
简单讲讲链剖吧.....就是把树边划分为轻重边，重边的定义是和siz最大的儿子之间的边
通过两次dfs实现，可以证明重链（重边形成的链）不超过logn条
直接上代码吧，复杂度O(nlogn^2)
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Mx=10010; struct Edge { int x,y,val; } edge[Mx]; struct Tree { int l,r,val; } tree[4*Mx]; int n,cnt,dep[Mx],siz[Mx],fa[Mx],num[Mx],son[Mx],top[Mx];//top表示最近的重链父节点 int tot,nxt[2*Mx],head[Mx],ver[2*Mx],val[2*Mx]; void clear() { memset(head,0,sizeof(head)); memset(son,0,sizeof(son)); cnt=0;tot=0; } inline void add(int x,int y,int z) { tot++; nxt[tot]=head[x]; ver[tot]=y; val[tot]=z; head[x]=tot; } //链剖 void dfs1(int u,int Fa,int Dep) { dep[u]=Dep,siz[u]=1,son[u]=0,fa[u]=Fa; for(int i=head[u];i;i=nxt[i]) { int v=ver[i]; if(v==Fa) continue; dfs1(v,u,Dep+1); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } } void dfs2(int u,int Top) { top[u]=Top,num[u]=++cnt; if(son[u]) dfs2(son[u],Top); for(int i=head[u];i;i=nxt[i]) { int v=ver[i]; if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } //线段树 void pushup(int x) { tree[x].val=max(tree[x<<1].val,tree[x<<1|1].val); } void build(int l,int r,int v) { tree[v].l=l;tree[v].r=r; if(l==r) { tree[v].val=val[l]; return ; } int mid=(l+r)>>1; build(l,mid,v*2); build(mid+1,r,v*2+1); pushup(v); } void update(int u,int v,int val) { if(tree[u].l==tree[u].r) { tree[u].val=val; return ; } int mid=(tree[u].l+tree[u].r)/2; if(v<=mid) update(u*2,v,val); else update(u*2+1,v,val); pushup(u); } int query(int x,int l, int r) { if(tree[x].l>=l&&tree[x].r<=r) return tree[x].val; int ans=0,mid=(tree[x].l+tree[x].r)/2; if(l<=mid) ans=max(ans,query(x<<1,l,r)); if(r>mid) ans=max(ans,query(x<<1|1,l,r)); return ans; } int solve(int u,int v) { int ans=0,Top1=top[u],Top2=top[v]; while(Top1!=Top2) { if(dep[Top1]<dep[Top2]) swap(Top1,Top2),swap(u,v); ans=max(ans,query(1,num[Top1],num[u])); u=fa[Top1];Top1=top[u]; } if(u==v) return ans; if(dep[u]>dep[v]) swap(u,v); ans=max(ans,query(1,num[son[u]],num[v])); return ans; } int main() { int T;scanf("%d",&T); while(T--) { clear(); scanf("%d",&n); for(int i=1,x,y,z;i<n;i++) { scanf("%d%d%d",&x,&y,&z); edge[i].x=x;edge[i].y=y;edge[i].val=z; add(x,y,z);add(y,x,z); } dfs1(1,0,1);dfs2(1,1); for(int i=1;i<n;i++) { if(dep[edge[i].x]<dep[edge[i].y]) swap(edge[i].x,edge[i].y); val[num[edge[i].x]]=edge[i].val; } build(1,cnt,1); while(1) { char s[200];scanf("%s",s);if(s[0]=='D') break; int x,y; scanf("%d%d",&x,&y); if(s[0]=='Q') printf("%d ",solve(x,y)); if (s[0]=='C') update(1,num[edge[x].x],y); } } return 0; }
Qtree Ⅱ
题意：https://vjudge.net/problem/SPOJ-QTREE2
路径查询距离、第K个点
sol ：本来想都没想直接写了个链剖，结果发现不用QAQ
这应该是Qtree1~7里最水的吧QAQ，直接倍增就行了
预处理每个点到根的路径长度，第一问求出lca后直接输出dis[x]+dis[y]-2dis[lca]即可
第二问需要考虑是在x-lca的路径上还是y-lca的路径上，然后直接倍增求第k个祖先即可
P.S.这里可以扩展一下，广义的树上倍增，orz集训队dalao
可以有O(D * N ^ ((Ｄ+1)/Ｄ))的时间的预处理。
设Ｋ＝N^(1/D)，预处理出所有点分别的第i*K^j个祖先(对于所有1<=i<K且0<=j<D)。
然后每次求时将要跳的步数转化成一个不超过Ｄ位的Ｋ进制数就可以在O(D)的时间内求出来啦。
我们平时在说的倍增(预处理出每个点的第1,2,4,8,16,...个祖先)是D=log2(N),K=2的特例。
Ｄ的值可以根据需要调整。
话说，我一开始还wa了半天，结果发现是return 0打到了while(T--)里面QAQ
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Mx=10010; int n,len,tmp,fa[Mx],fa1[Mx][30],dep[Mx],val[Mx]; int tot,head[Mx],nxt[2*Mx],ver[2*Mx],val1[2*Mx]; void clear() { tot=0; memset(head,0,sizeof(head)); memset(val,0,sizeof(val)); memset(fa1,0,sizeof(fa1)); } inline void add(int x,int y,int z) { tot++; nxt[tot]=head[x]; ver[tot]=y; val1[tot]=z; head[x]=tot; } void dfs(int u,int Fa,int Val,int Dep) { dep[u]=Dep,fa[u]=Fa,val[u]=val[Fa]+Val; for(int i=head[u];i;i=nxt[i]) { int v=ver[i]; if(v==Fa) continue; dfs(v,u,val1[i],Dep+1); } } void pre() { for(int i=1;i<=n;i++) fa1[i][0]=fa[i]; for(int j=1;1<<j<=n;j++) for(int i=1;i<=n;i++) fa1[i][j]=fa1[fa1[i][j-1]][j-1]; } int find_lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(tmp=0,len=0;(1<<tmp)<=dep[x];tmp++); tmp-=1; for(int j=tmp;j>=0;j--) if(dep[x]-(1<<j)>=dep[y]) x=fa1[x][j]; if(x==y) return x; for(int j=tmp;j>=0;j--) if(fa1[x][j]!=-1&&fa1[x][j]!=fa1[y][j]) x=fa1[x][j],y=fa1[y][j]; return fa1[x][0]; } int find_fa(int x,int k) { int Dep=dep[x]-k+1; for(tmp=0;(1<<tmp)<=dep[x];tmp++); tmp--; for(int j=tmp;j>=0;j--) { if(dep[x]==Dep) break; if(dep[fa1[x][j]]>=Dep) x=fa1[x][j]; } return x; } int main() { int T;scanf("%d",&T); while(T--) { clear(); scanf("%d",&n); for(int i=1,x,y,z;i<n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } fa[1]=1;dfs(1,1,0,1);pre(); while(1) { char ch[30];scanf("%s",ch); if(ch[1]=='O') break; if(ch[0]=='D') { int x,y,lca; scanf("%d%d",&x,&y); lca=find_lca(x,y); printf("%d ",val[x]+val[y]-(2*val[lca])); } else { int x,y,k,lca;scanf("%d%d%d",&x,&y,&k); lca=find_lca(x,y); if(dep[x]-dep[lca]+1>k) printf("%d ",find_fa(x,k)); else printf("%d ",find_fa(y,dep[y]+dep[x]-(2*dep[lca])+2-k)); } } } return 0; }
Qtree Ⅲ
题意：https://vjudge.net/problem/CodeChef-QTREE
给一棵树，黑白染色，有两个操作：单点颜色修改、查询1~v的路径上最先出现黑点的位置
sol ：显然LCT可做