搜索结果
查询Tags标签： 树上，共有 25条记录-
P3177 树上染色做题记录
树形 dp 好题。 做这题的思想历程： 定义 \(dp_{i,j}\) 表示以 \(i\) 为根的子树中，选择了 \(j\) 个节点的答案。感觉还要带上一维状态就是所有黑点距离 \(i\) 的距离，这违反了做题思路中间的简洁性的原则。于是我们 查看题解。 经过不明方法之后，我们想到了定义 \(dp_…
2022/9/17 23:16:14 人评论 次浏览 -
CSP-S2019 树上的数（并查集，dfs）
CSP-S2019 树上的数 \(n\) 树。\(n\) 排列卡片。\(i\) 卡片初始在 \(p_i\)。每次删一条边可以交换两端卡片。删光边最后卡片 \(i\) 位置 \(P_i\)。求字典序最小 \(P\)。 CODE 无可奉告。
2022/9/15 23:17:21 人评论 次浏览 -
树上最长路的O(n)算法
关于如何求得树中每个点最长路的O(n)算法： 1.算法流程：求出树上的直径，在第二次dfs中求出从直径一端点到每个点的距离 再跑一次dfs，求出另一端点到每个点的距离，并更新每个点的最长路2. 算法实现： #include<bits/stdc++.h> #define ll long long #define N 10…
2022/9/6 14:32:41 人评论 次浏览 -
LCA（树上倍增）
https://www.luogu.com.cn/problem/P3379链式前向星存边 fa[i][j] 代表从i结点向上找 2^i 代的父亲，（i=0代表真父亲） dfs从根结点开始fa[now][i] = fa[fa[now][i - 1]][i - 1];代表当前结点的第2^i代父节点是当前结点2^(i-1)父节点的2^(i-1)代父节点，然后再对其连接到…
2022/7/31 23:42:40 人评论 次浏览 -
AC 自动机
重新学 \(AC\) 自动机发现以前就像没见过一样…… 首先是一段经典的话：“\(AC\) 自动机是 \(trie\) 树上跑 \(kmp\)” 于是 \(AC\) 自动机的关键在于运用 \(nxt\) 进行匹配 由于这时的 \(nxt\) 形成一棵树形结构，可以将一些匹配问题转化为树上问题 如果 \(x\) 匹配到了文…
2022/7/26 23:23:46 人评论 次浏览 -
树上分治
1. 点分治 现在有一棵大小为 \(n\) 的树，要求出路径长度小于 \(k\) 的路径。 每次可以通过选择重心的方式，将整棵树分为一堆不大于 \(\dfrac{n}{2}\) 的子树，所以将整棵树分为大小为 \(1\) 的子树需要 \(\log n\) 次。 对于现在求出重心的子树，显然有三种情况可以组成…
2022/7/25 23:24:18 人评论 次浏览 -
树上差分
本篇随笔简单讲解一下信息学奥林匹克竞赛中树上差分的相关知识点。树上差分近几年成为了考试热门，也成为了考察差分思想比较常用的手段。理解树上差分最好需要读者了解图和树的基础知识，\(LCA\)及\(LCA\)问题的求法，以及差分数组和差分思想。 一、边的差分 我们对差分和…
2022/3/30 23:24:21 人评论 次浏览 -
点分树学习笔记
1.0 定义 其实本质也是一种暴力。。 回忆点分治的过程：每次找到当前子树的重心，处理所有经过该重心的路径的答案，然后将其删去，分裂成一些子树，再分别进去递归。 把点分治的过程离线下来，将当前树的重心与上一层的树的重心连边，这样就可以得到一棵树，我们称之为“…
2022/2/6 23:12:38 人评论 次浏览 -
HNOI2022 树上问题
考点基环树 树链剖分 树上DP 树上分治点分治NOTE 1.分治前求dep的时候忘记dep[rt]=0流程1(适用于计数等容易去重的)找根 处理过当前根到子树内的路径(加入根到根的路径，用两条到根的路径合并) 去掉不合法(统计同一个子树出来到当前根的两条路径)，继续分治流程2(适用于最…
2021/12/17 23:28:45 人评论 次浏览 -
HNOI2022 树上问题
考点基环树 树链剖分 树上DP 树上分治点分治NOTE 1.分治前求dep的时候忘记dep[rt]=0流程1(适用于计数等容易去重的)找根 处理过当前根到子树内的路径(加入根到根的路径，用两条到根的路径合并) 去掉不合法(统计同一个子树出来到当前根的两条路径)，继续分治流程2(适用于最…
2021/12/17 23:28:45 人评论 次浏览 -
[CSP-S2019] 树上的数 树上推理
还没整完明天再说，靠不小心点了发布、、 Link 某些废话 devinwang勒令我们补掉CSP2019的题 /youl 看了半天题解脑子里还是浆糊，退役人是我这样的。 这篇题解写的非常清楚，我写这个只是给我自己看。 题意 现在给你一棵树，数字 \(i\) 在编号为 \(p_i\) 的节点上。 每次删…
2021/11/7 23:15:36 人评论 次浏览 -
[CSP-S2019] 树上的数 树上推理
还没整完明天再说，靠不小心点了发布、、 Link 某些废话 devinwang勒令我们补掉CSP2019的题 /youl 看了半天题解脑子里还是浆糊，退役人是我这样的。 这篇题解写的非常清楚，我写这个只是给我自己看。 题意 现在给你一棵树，数字 \(i\) 在编号为 \(p_i\) 的节点上。 每次删…
2021/11/7 23:15:36 人评论 次浏览 -
笛卡尔树学习笔记
笛卡尔树本质是一种 \(treap\)，可以线性构建，在构造数据下并不平衡 对于一个排列，其笛卡尔树 \(dfs\) 序为下标，其权值满足小（大）根性质 笛卡尔树可以很好地把序列问题转化为树上问题，其好处在于很方便地利用树上左右子树大小进行处理 笛卡尔树与数列的对应关系：区…
2021/10/13 23:17:42 人评论 次浏览 -
笛卡尔树学习笔记
笛卡尔树本质是一种 \(treap\)，可以线性构建，在构造数据下并不平衡 对于一个排列，其笛卡尔树 \(dfs\) 序为下标，其权值满足小（大）根性质 笛卡尔树可以很好地把序列问题转化为树上问题，其好处在于很方便地利用树上左右子树大小进行处理 笛卡尔树与数列的对应关系：区…
2021/10/13 23:17:42 人评论 次浏览 -
题解 树上竞技
传送门 有几档暴力不会写，巨丢人 \(m=2\) 的话两个人之间的距离会覆盖整棵树上所有可能的路径，所以就是求所有树上路径长度的总和 成链且 \(m\) 为奇数的话，集中点肯定是中位数那个点 考场上想偏了，只会用这个性质求一些给定的人应该集中在哪个点 但实际上可以枚举中位…
2021/10/3 6:40:11 人评论 次浏览
