TitanZhang

分类

算法浅谈(1) 题解(48)

/ 注册

TA的专栏 47篇文章 1人订阅

2020牛客暑期多校训练营

47篇文章 1255人学习

全部文章（共2篇）

树形DP-虚树的思路&例题

虚树入门前置知识掌握求lca，dfs序，每个点的深度，两点之间的距离等操作什么是虚树虚树的核心思想，就是保留一棵树上有用的&关键的点，重新构建一棵“虚”树，更加快速地跑带关键点的树形dp。怎么用虚树这里就需要用到上面提到的求lca(最近公共祖先)技术。我们对一棵虚树的要求是，节点...

虚树树形dp

2020-08-01

1 748

2020牛客暑期多校训练营（第一场）B-Infinite Tree 来自专栏

题目大意定义为n的最小质因子，构造一棵无限的树，树上每个n(n>1)与相连。定义为到间的边的数量（距离），给出与数组，求出。解题思路一本题因为树上节点过多，用虚树来优化树形dp是一种方法。所以，我们可以虚树二次扫描换根，求解树的带权重心来得到答案。带权重心介绍：https://b...

虚树树形DP 换根

2020-07-30

1 975