进食后人(尤其是生成树+lca 10分的)
查看原帖
进食后人(尤其是生成树+lca 10分的)
559442
GWBailang楼主2024/12/23 22:33

样例和hack数据都水死了……

  • 题目给的图并不一定连通,不能只跑一出颗生成树。
  • 预处理倍增数组时一定要注意按照树上从根往下推的顺序,不要向我这样直接从1~n跑了一遍:
    for(int i=1;i<=n;i++){
          int p=fa[0][i];
          for(int j=1;j<=KMAX;j++){
              bq[j][i]=min(bq[j-1][i],bq[j-1][p]);
              fa[j][i]=p=fa[j-1][p];
          }
      }
    
  • 倍增时别把记录father和记录最小边权的数组用混了。
2024/12/23 22:33
加载中...