社区讨论
95分代码求指点!查了一天
P4149[IOI 2011] Race参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi7wi7ww
- 此快照首次捕获于
- 2025/11/21 04:45 4 个月前
- 此快照最后确认于
- 2025/11/21 04:45 4 个月前
简要说明一下,常规点分治做法。先处理经过点p的路径,再继续处理子树。其中统计路径用的是,把距离放进Temp数组,然后排序再进行扫描各种处理。问题出在分治函数这一块。
CPPvoid 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 条回复,欢迎继续交流。
正在加载回复...