一种大树变小树的方法。大概就是只保留题目要求的关键点和其他一些统计答案必须的点,把剩余的所有点从树上砍掉。原理是维护一条最右链(就是我们扫到的最右边的一条链,它左边的虚树已经建好)。
具体的操作:
首先把所有的关键点按照dfs序排序。然后开始分讨:
上个代码,大概写写注释。
bool cmp(int a,int b){return dfn[a]<dfn[b];} int main(){ scanf("%d",&k); for(int i=1;i<=k;i++){ scanf("%d",&h[i]);v[h[i]]=true; } sort(h+1,h+k+1,cmp);//按dfs序排序 top=0; for(int i=1;i<=k;i++){ if(!top){ stk[++top]=h[i];continue;//栈空 直接进栈 } int x=h[i],lc=lca(x,stk[top]); while(true){ if(dep[lc]>=dep[stk[top-1]]){ if(lc!=stk[top]){ add(lc,stk[top]); if(lc!=stk[top-1])stk[top]=lc; else top--; } break;//lca向栈顶连边 同时退栈 } else{ add(stk[top-1],stk[top]);//栈内元素互相连边 退栈 top--; } } stk[++top]=x;//当前节点入栈 } while(--top)add(stk[top],stk[top+1]);//栈内元素互相连边 dp(stk[1]);//开始运行普通的树形dp }
至于边权问题,这个因题而异,大概和你的dp方程有点关系。不再多说了。