首页 > Tree Requests
开通博客写题解
头像 lifehappy
发表于 2020-11-07 16:51:06
Tree Requests 经典的树上启发式合并题目了（其实就是瞎暴力）。 对于一颗有根树，我们先做一次dfs找到每个节点的重儿子，然后在答案统计的时候优先遍历轻儿子，不保留答案，最后遍历重儿子保留答案。 这颗树显然我们要维护的信息就是每一层字母的奇偶性，所以我们直接在每一层开一个30大小的bits 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Kur1su
发表于 2020-11-12 16:51:14
Description 给一棵树，无修改操作，每次查询给出 (l,r)，查询 l 的子树在深度为 r 的节点对应的字母能不能构成回文串。 Solution 思路：dsu on tree(树上启发式合并)算法的本质其实就是一个优化暴力的过程。按暴力的想法去统计，每次统计所有子树，再删除贡献，时间复杂度 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 zzugzx
发表于 2020-11-11 13:59:44
树上启发式合并，多用于对子树的暴力询问，通过使用轻重链定义来进行优化，将算法复杂度降到算是一种优雅的暴力 先用一道dsu on tree比较模版的题来引一下codeforces 600E题意： 一棵树n个点，每个点有一个颜色 要求每个结点子树的出现哪个颜色次数最多 如果有多个颜色次数同时最多，结 展开全文
去ta的博客 赞 (5) 回复(3) 收起
头像 林思艺
发表于 2020-11-10 09:42:45
题意 给你一棵有 个节点以 为根的树，每个节点为 的任意字母。有 次询问，每次询问给出 ，指以 为根的子树内深度为 的所有节点的字母在排列后能否构成一个回文串。 分析 要排列后成为回文串，所以在符合条件的所有节点之中至多只有一种字母的数量为奇数个，其余的字母数量必定均为偶数个。因为回文 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 DeNeRATe
发表于 2020-11-18 21:06:24
分析 本人只会两种做法——dsu on tree and 按深度处理这里，我说一下码量比较小的第二种做法把（时间复杂度一样） 首先我们每次需要拉出来的是一棵子树内的深度为x的那些点所以我们容易发现能够被拉出来当且仅当，这个点深度为x且那么我们可以考虑维护每个深度的每种字母的dfn集合然后就可以在的时 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 rk_no
发表于 2020-11-07 16:27:23
题目： 给一棵树，每个点有一个英文字母。次询问，问子树内所有深度为的点里的字母能否重排成一个回文串。 做法： 处理子树上的询问，不带修改，询问可离线，我们可以考虑用。这是一种统计子树信息的方式，通过调整顺序，保留重儿子中的信息来优化复杂度。在这个题里，我们要做的就是对每棵子树，得到数组，代表这棵子 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 昵称很长很长真是太好了
发表于 2020-11-18 21:18:23
题意：给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问 a,b 查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.题解：dfs序+状态压缩+二分查找这个题用到了很多小技巧，比如说异或前缀和等等。我们首先对他跑 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 sunsetcolors
发表于 2020-11-09 22:32:48
Tree Requests 题目地址: https://ac.nowcoder.com/acm/problem/111044 基本思路: 有对每个子树下的查询,但没有修改,考虑，我们先将查询离线,并且预处理出深度,对于每一棵子树我们统计一下每种深度下每个字母的出现次数,由题意我们知道只要在某 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 回归梦想
发表于 2020-11-28 11:31:05
题意： 一棵树，每个节点是一个字母跟节点深度为1问对于x的子树，深度为y的节点能否组成回文串？ 题解： 这个题处处都是细节组成回文串的话，要求至多只有一个字母出现奇数次我们先用dfs序给树标上号，同时开vector按照顺序存下每一层的节点以及每一层in[x]对于每一层，我们已经知道有什么节点，然后把 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”