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=;
struct Edge { int x,y,val; } edge[Mx];
struct Tree { int l,r,val; } tree[*Mx];
int n,cnt,dep[Mx],siz[Mx],fa[Mx],num[Mx],son[Mx],top[Mx];//top表示最近的重链父节点
int tot,nxt[*Mx],head[Mx],ver[*Mx],val[*Mx];
void clear()
{
memset(head,,sizeof(head));
memset(son,,sizeof(son));
cnt=;tot=;
}
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]=,son[u]=,fa[u]=Fa;
for(int i=head[u];i;i=nxt[i])
{
int v=ver[i];
if(v==Fa) continue;
dfs1(v,u,Dep+);
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<<].val,tree[x<<|].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)>>;
build(l,mid,v*); build(mid+,r,v*+);
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)/;
if(v<=mid) update(u*,v,val);
else update(u*+,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=,mid=(tree[x].l+tree[x].r)/;
if(l<=mid) ans=max(ans,query(x<<,l,r));
if(r>mid) ans=max(ans,query(x<<|,l,r));
return ans;
}
int solve(int u,int v)
{
int ans=,Top1=top[u],Top2=top[v];
while(Top1!=Top2)
{
if(dep[Top1]<dep[Top2]) swap(Top1,Top2),swap(u,v);
ans=max(ans,query(,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(,num[son[u]],num[v]));
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
clear();
scanf("%d",&n);
for(int i=,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(,,);dfs2(,);
for(int i=;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(,cnt,);
while()
{
char s[];scanf("%s",s);if(s[]=='D') break;
int x,y; scanf("%d%d",&x,&y);
if(s[]=='Q') printf("%d\n",solve(x,y));
if (s[]=='C') update(,num[edge[x].x],y);
}
}
return ;
}
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=;
int n,len,tmp,fa[Mx],fa1[Mx][],dep[Mx],val[Mx];
int tot,head[Mx],nxt[*Mx],ver[*Mx],val1[*Mx];
void clear()
{
tot=;
memset(head,,sizeof(head));
memset(val,,sizeof(val));
memset(fa1,,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+);
}
}
void pre()
{
for(int i=;i<=n;i++) fa1[i][]=fa[i];
for(int j=;<<j<=n;j++)
for(int i=;i<=n;i++)
fa1[i][j]=fa1[fa1[i][j-]][j-];
}
int find_lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(tmp=,len=;(<<tmp)<=dep[x];tmp++); tmp-=;
for(int j=tmp;j>=;j--)
if(dep[x]-(<<j)>=dep[y]) x=fa1[x][j];
if(x==y) return x;
for(int j=tmp;j>=;j--)
if(fa1[x][j]!=-&&fa1[x][j]!=fa1[y][j])
x=fa1[x][j],y=fa1[y][j];
return fa1[x][];
}
int find_fa(int x,int k)
{
int Dep=dep[x]-k+;
for(tmp=;(<<tmp)<=dep[x];tmp++); tmp--;
for(int j=tmp;j>=;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=,x,y,z;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
fa[]=;dfs(,,,);pre();
while()
{
char ch[];scanf("%s",ch);
if(ch[]=='O') break;
if(ch[]=='D')
{
int x,y,lca; scanf("%d%d",&x,&y);
lca=find_lca(x,y);
printf("%d\n",val[x]+val[y]-(*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]+>k) printf("%d\n",find_fa(x,k));
else printf("%d\n",find_fa(y,dep[y]+dep[x]-(*dep[lca])+-k));
}
}
}
return ;
}
Qtree Ⅲ
题意：https://vjudge.net/problem/CodeChef-QTREE
给一棵树，黑白染色，有两个操作：单点颜色修改、查询1~v的路径上最先出现黑点的位置
sol ：显然LCT可做