求问树上倍增
  • 板块学术版
  • 楼主BFSDFS123
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/11/17 18:18
  • 上次更新2023/11/17 18:33:18
查看原帖
求问树上倍增
358739
BFSDFS123楼主2023/11/17 18:18

RT。本人技艺不精,求问一个问题。

void dfs(int u,int fat)
{
    fa[u][0]=fat;
    for(int i=1;i<=20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:G[u])
        dfs(v,u)
}

以上这段代码,可以计算出正确的倍增数组,但是为什么将

for(int i=1;i<=20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];

挪到递归后面计算就会出错,求问。

2023/11/17 18:18
加载中...