文件名称：参考代码(建虚树)-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2024-05-14 23:11:52
动态规划
参考代码：(建虚树) for (int i=1;i<=m;i++){ if (!tot){ stack[++tot]=store[i]; father[store[i]]=0;}//最右链上无节点 else{ int lca=Lca(stack[tot],store[i]); father[store[i]]=lca; for (;deep[stack[tot]]>deep[lca];tot--){ if (deep[stack[tot-1]]<=deep[lca]) father[stack[tot]]=lca;// }//弹栈，弹到栈顶元素不比新节点的父亲深为止，同时更新father。 if (stack[tot]!=lca){ father[lca]=stack[tot]; store[++cnt]=lca; stack[++tot]=lca;} stack[++tot]=store[i]; }//在最右链上寻找新节点的父亲，更新最右链 }