【文件属性】：
文件名称：参考代码(建虚树)-动态规划-树型DP经典课件
文件大小：4.26MB
文件格式：PPT
更新时间：2021-04-25 05:25:12
动态规划
参考代码：(建虚树)
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];
}//在最右链上寻找新节点的父亲，更新最右链
}