nihility
  文章分类
数据结构 5 字符串 3 图论 2 动态规划 1 Golang 3
虚树 虚树
先由一道例题引入：消耗战 对于这个问题的每个询问，我们直接树形$DP$就很容易解决了，然而，问题就在于如果我们每次$DP$都遍历整个树，那时间复杂度就爆炸了，但我们发现我们每次询问涉及到的点很少，这时就引入了我们的虚树，我们只需要把我们需要
2022-08-29 图论
虚树
前后缀和优化建图 前后缀和优化建图
先把遇到的问题放出来，然后再解决问题。 题目链接：Riddle 很明显，这是一道$2-SAT$问题，每条边至少有一个端点是关键点，若我们用$x$表示$x$是关键点，$x+n$表示$x$不是关键点，则对于一条边$x-y$，我们可以得到$x+n
2022-08-24 图论
前后缀和优化建图