虚树
2022/9/3 23:22:58
本文主要是介绍虚树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一种大树变小树的方法。大概就是只保留题目要求的关键点和其他一些统计答案必须的点,把剩余的所有点从树上砍掉。原理是维护一条最右链(就是我们扫到的最右边的一条链,它左边的虚树已经建好)。
具体的操作:
首先把所有的关键点按照dfs序排序。然后开始分讨:
- 如果栈空则节点入栈。
- 找到该点与栈顶的lca。
- 如果lca的深度比栈顶下面第一个节点大且lca不是栈顶(也就是说lca在栈顶和栈顶下面第一个节点中间夹着),则将lca连一条到栈顶的边;之后栈顶出栈,lca进栈(显然如果此时栈顶是lca则不用操作)
- 如果不是,直接从栈顶下面第一个节点向栈顶连边,栈顶出栈,循环到第3步。
- 该节点进栈。
- 扫描完所有节点后,顺序将栈内元素连边。
上个代码,大概写写注释。
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方程有点关系。不再多说了。
这篇关于虚树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-0601-电商商品中心解密:仅凭SKU真的足够吗?
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能