一个小问题,刚学OI
  • 板块P4178 Tree
  • 楼主JK_LOVER
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/9/3 19:34
  • 上次更新2023/11/5 13:46:54
查看原帖
一个小问题,刚学OI
227824
JK_LOVER楼主2020/9/3 19:34

这是树上启发式合并的代码

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);
}
2020/9/3 19:34
加载中...