Rt,在写重链剖分的时候如果我使重链长度大于n使裂开为什么会WA?
void dfs(int x,int y){
top[x] = y;
dfn[x] = ++tot;
//add(1,1,n,tot,a[x]);
add(head[y],Log,a[x]);
if(son[x]){
//if(d[x] - d[y] <= Q) dfs(son[x],y);
//else dfs(son[x],son[x]);这里,下面就AC了
dfs(son[x],y);
}
for(int to:e[x]) if(to != fa[x] && to != son[x]) dfs(to,to);
R[x] = tot;
}
然后是求处理链上的代码:
int find(int x,int y,int z){
int tx = top[x],ty = top[y],fx = 1,fy = 1,mx = 0;
while(tx != ty){
if(d[tx] > d[ty]){
if(fx){
mx = max(mx,get(x,tx,z));
fx = 0;
} else mx = max(mx,ask(head[tx],Log,z));
x = fa[tx];
} else {
if(fy){
mx = max(mx,get(y,ty,z));
fy = 0;
} else mx = max(mx,ask(head[ty],Log,z));
y = fa[ty];
}
tx = top[x],ty = top[y];
}
if(d[x] < d[y]) swap(x,y);
mx = max(mx,get(x,y,z));
return mx;
}