社区讨论

95分代码求指点!查了一天

P4149[IOI 2011] Race参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi7wi7ww
此快照首次捕获于
2025/11/21 04:45
4 个月前
此快照最后确认于
2025/11/21 04:45
4 个月前
查看原帖
简要说明一下,常规点分治做法。先处理经过点p的路径,再继续处理子树。其中统计路径用的是,把距离放进Temp数组,然后排序再进行扫描各种处理。问题出在分治函数这一块。
CPP
void work(int Size, int X){
	Min_Part = Size;
	getpart(X, Size); //这两行求重心root
	
	//Dis[root] = 0; 这里是重点,理论上应该是需要重设为0的,因为处理子树问题应该是一个独立了的问题。事实上加这句会导致WA掉一个点
    
    
	Is_Delete[ Temp[Temp_tot=1] = Belong[root] = root] = 1;
	//信息更新
    
   //中间省略了统计经过重心的路径部分,包括dfs信息和扫描Temp,方便大佬观看...这里的dfs处理了以root为根的子树节点到root的信息。也就是说,root节点的信息,dis,cnt等是上一个分治时候的, root到 p的距离。下面画个图。
	
	//继续分治
	for(int i = head[root]; i; i = e[i].nex){
		int v = e[i].v;
		if(Is_Delete[v]) continue; //已经删点的标记
		work(TreeSize[v], v);
	} 
}
那么问题来了,假设root保留了对p的信息。那么就长这样。
图
保留的这个dis信息只有一个用,就是影响Temp里存的dis,从而影响了我的ans统计。 不把dis[root]赋值为0,则Temp里面会多一个root到p的距离len,少一个0。
这个距离理应在统计过p的时候已经对答案产生贡献了。即使假设这个len是有用的,那我的节点到root的路径也不是简单路径了,我想不通!

回复

4 条回复,欢迎继续交流。

正在加载回复...