回归梦想
回归梦想
全部文章
分类
dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)
归档
标签
去牛客网
TA的专栏 41篇文章 0人订阅
XCPC
16篇文章 978人学习
牛客每日一题
6篇文章 776人学习
项目笔记
0篇文章 0人学习
数据结构
0篇文章 0人学习
图论
0篇文章 0人学习
数论
3篇文章 685人学习
ACwing寒假每日一题（提高组）
3篇文章 780人学习
codeforces
13篇文章 912人学习
全部文章 （共4篇）

CF613D Kingdom and its Cities

CF613D Kingdom and its Cities 题目： 给定一棵有n 个节点的树，树上有一些关键点(key)。接下来有q组询问，每次给出ki 个key，要求删去一些点，使得这些key不相连。要求删去的最少的点数。 1<=n<=100000 1<=q<=100000...
虚树 树形dp ***
2021-02-23
0 652

Infinite Tree 来自专栏

Infinite Tree 题意： 题解： 参考博客看了好一阵子才明白。。。emm。我们先按照题意画出一部分树我们先不考虑复杂度，这题应该怎么做？题目给了每个点的权值w[i]，问一个点到所有的节点路径长度*点权之和最小是多少，很明显是树形dpdp[i]表示以i为根的子树到i的w和sum[i]表示乘...
树状数组 虚树 *****
2021-02-23
0 746

[SDOI2011]消耗战

[SDOI2011]消耗战 题意： 给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少. 题解： 树型dp+虚树dp[x]:切断x及其子树上询问点的最小代价预处理出minv[pos]代表从11到pos路径上最小的边权如果pos...
dfs序 **** 虚树
2021-01-21
0 644

（神奇的）虚树（初步了解）

参考文献：博文1博文2博文3 引入 在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值. 如果我们直接在整颗树上进行dp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际规模相关就好了...
虚树 ***
2021-01-21
0 551
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号