回归梦想

分类

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人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共7篇）

[SDOI2011]消耗战

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

dfs序 **** 虚树

2021-01-21

0 644

Tree Requests

题意：一棵树，每个节点是一个字母跟节点深度为1问对于x的子树，深度为y的节点能否组成回文串？题解：这个题处处都是细节组成回文串的话，要求至多只有一个字母出现奇数次我们先用dfs序给树标上号，同时开vector按照顺序存下每一层的节点以及每一层in[x]对于每一层，我们已经知道有什么节点，然后把...

dfs序 **** 思维二进制

2020-11-28

2 615

NC204871 求和

题目描述已知有 n 个节点，有 n−1 条边，形成一个树的结构。给定一个根节点 k，每个节点都有一个权值，节点i的权值为vi。给 m 个操作，操作有两种类型：1 a x ：表示将节点 aa 的权值加上 x2 a ：表示求 a 节点的子树上所有节点的和（包括 a 节点本身）题解：通过dfs序将...

树状数组 dfs序线段树 ***

2020-11-27

2 569

H 数据只搬样例

题意：一个树，对其有两个操作，操作1是将节点a的权值增加x操作2是查询节点a到根节点R的简单路径上所有节点的权值的平方的和答案对2^取模题解：如果ull类型的整数溢出了，就相当于取模2^64了。因为ull的范围是[0,2^64-1]，所以直接开unsigned long long就行有两个方法...

**** 树链剖分 dfs序线段树

2020-11-23

1 533

Cover the Tree（2020多校第二场C）

Cover the Tree@[toc] 题意：一个无向树，选择最少数量的链子，能将树上所有边覆盖，答案不唯一(1≤n≤2×10^5^）链子就是两点之间的边看看样例输入 5 1 2 1 3 2 4 2 5 输出 2 2 3 4 5 一种情况如图所示：所有边被覆盖的链子有：链子2->3:覆盖了...

dfs序树上dp DFS序

2020-07-24

0 0

牛客网【每日一题】7月8日 Alliances

来源：牛客网@[toc] 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径...

dfs序 lca

2020-07-09

0 422

欧拉序与DFS序

@[TOC]欧拉序与DFS序相似又不同欧拉序的定义树在dfs过程中的节点访问顺序称为欧拉序.那有人会问：dfs序和欧拉序啥区别？ dfs序：是指将一棵树被dfs时所经过的节点顺序（不绕回原点）。欧拉序：就是从根结点出发，按dfs的顺序在绕回原点所经过所有点的顺序。欧拉序与dfs序不同地方在于，欧...

dfs序欧拉序

2020-05-01

0 1304