首页 > New Year Tree
开通博客写题解
头像 Kur1su
发表于 2021-01-17 17:07:39
Description 给一棵树，根为1，每个节点有一种颜色，有两种操作： 将该节点x及其子树的颜色都变为y 查询节点x及其子树有多少种颜色 Solution 颜色的范围为 (), 不妨用二进制上的每一位去代表每一种颜色是否存在那么检查有多少种颜色只需要统计二进制的1个数，用函数 即可由于是树 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 shyyhs
发表于 2021-01-15 17:13:00
回去再调. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+5; ll col[N]; vector<int>g[N]; int now[N],last[N 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 sunrise__sunrise
发表于 2021-01-19 22:25:34
题目描述 给你的一棵树，每个节点有自己的颜色。下面有两种操作。操作一：把一个节点及其子树全部改成颜色。操作二：输出一个节点及它子树中一共有几种颜色。题目涉及的颜色种类。 Solution 观察颜色种类就是这个题目的切入点，看到最大不超过种的颜色，就在指引我们去状压这个颜色了。那么维护数上子节点，这个 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 lifehappy
发表于 2021-01-13 19:47:59
New Year Tree 首先看到颜色的范围是，容易想到用二进制数来存储，二进制的第i位表示是否有第i种颜色 接下来我们只要求得整棵树的序，然后维护一个异或线段树即可，支持区间修改，区间查询即可，比较套路的裸题吧。 #include <bits/stdc++.h> #define mi 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunsetcolors
发表于 2021-01-14 17:18:38
CF620E New Year Tree 题目地址： https://ac.nowcoder.com/acm/problem/111259 基本思路： 我们发现颜色最多只有种,所以明显我们可以用二进制串来表示每种颜色, 并且因为操作中只有对子树的修改,所以我们直接序+线段树维护一下二进制状态 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-01-14 21:25:05
关于子树的修改和查询 很容易想到树链剖分 用序建立线段树 线段树中保存每个节点的颜色信息 由于颜色最多种所以可以压缩为二进制数 然后维护一个懒标记,就是裸题了 (另外,我是真不喜欢写树的题啊!!!!!) #include <bits/stdc++.h> using namespace s 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2021-01-15 12:07:45
题意： 给出一棵 n个节点的树，根节点为 1。每个节点上有一种颜色 ci。m次操作。操作有两种： 1 u c：将以 u为根的子树上的所有节点的颜色改为c。 2 u：询问以 u为根的子树上的所有节点的颜色数量。 题解：一看题目好像是个dfs序+线段树的板子题，但是需要思考的是，怎么查询一段区间的颜色数 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 MYCui_
发表于 2021-01-11 19:36:29
CF620E [New Year Tree] 前置知识： 线段树 + 状态压缩 + 子树 序 + 位运算小知识难度:3 ~ 4星 题目大意： (来自 Luogu 的翻译) 解题思路： 考虑到 很小 ，有经验的同学不难看出来这是状态压缩。 那么实际上这道题有三种写法，分别为： 不加优化的线段树 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”