在这个题解中
设 cost[i][j]cost[i][j]cost[i][j] 为节点 i 向上跳 2j2^j2j 步到达的节点的边权和,现在正 dfs 到节点 now 。
1.为什么有:
cost[now][i]=cost[fa[now][i−1]][i−1]+cost[now][i−1];cost[now][i]=cost[fa[now][i-1]][i-1]+cost[now][i-1];cost[now][i]=cost[fa[now][i−1]][i−1]+cost[now][i−1];
2.LCA函数里,为什么判断条件写成 if(depth[y]-(1<<i)>=depth[x]) ,即 ififif depth[y]−2i≥depth[x]depth[y]-2^i \geq depth[x]depth[y]−2i≥depth[x] ???
if(depth[y]-(1<<i)>=depth[x])
苦思无果,求路过dalao瞅瞅