这是树上启发式合并的代码
void solve(int x,int keep) {
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;if(y == son[x] || y == fa[x]) continue;
solve(y,0);
}
if(son[x]) solve(son[x],1);
Depp = dis[x];
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;if(y == son[x] || y == fa[x]) continue;
Ask(y);Add(y,1);
}
Ans += ask(rt,1,4e7,Depp,Depp+K);
update(rt,1,4e7,dis[x],1);
if(keep) return;
Add(x,-1);
}
这个是先处理重儿子,再处理轻儿子,再处理当前节点。这个是对的。那么为什么下面先处理当前节点的代码是错的????
void solve(int x,int keep) {
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;if(y == son[x] || y == fa[x]) continue;
solve(y,0);
}
if(son[x]) solve(son[x],1);
Depp = dis[x];
Ans += ask(rt,1,4e7,Depp,Depp+K);
update(rt,1,4e7,dis[x],1);
for(int i = head[x];i;i = e[i].nxt) {
int y = e[i].to;if(y == son[x] || y == fa[x]) continue;
Ask(y);
Add(y,1);
}
if(keep) return;
Add(x,-1);
}