A5304 | 奇怪的树
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
传说这座塔的房间与走廊像枝桠一样彼此相连，恰好构成一棵树，我们定义 $1$ 号房间为树的根。第 $u$ 个房间被染上颜色 $c_u$。Alice 手握一式“回响”，每次选定一个房间 $u$ 与阈值 $T$，就能让以 $u$ 为根的整片区域共鸣——只有当这片区域里某些颜色出现次数不少于 $T$ 时，仪式才会被放大奏效。
现在给出这棵树与所有查询 $(u,T)$，请你依次告诉 Alice：在每次选定的区域里，满足“出现次数至少为 $T$”的不同颜色有多少种。
现在给出这棵树与所有查询 $(u,T)$，请你依次告诉 Alice：在每次选定的区域里，满足“出现次数至少为 $T$”的不同颜色有多少种。
输入格式
* 第一行：两个整数 $n,q$——房间数与查询数。
* 第二行：$n$ 个整数 $c_1,c_2,\dots,c_n$，第 $u$ 个为房间的颜色。
* 接下来 $n-1$ 行：每行两个整数 $u,v$，表示房间 $u$ 与 $v$ 之间有一条无向走廊。
* 接下来 $q$ 行：每行两个整数 $u,T$，表示一次仪式查询。
* 第二行：$n$ 个整数 $c_1,c_2,\dots,c_n$，第 $u$ 个为房间的颜色。
* 接下来 $n-1$ 行：每行两个整数 $u,v$，表示房间 $u$ 与 $v$ 之间有一条无向走廊。
* 接下来 $q$ 行：每行两个整数 $u,T$，表示一次仪式查询。
输出格式
输出 $q$ 行，第 $i$ 行是第 $i$ 次查询的答案：以 $u$ 为根的区域中，出现次数不少于 $T$ 的不同颜色有多少种。
输入输出样例
输入 #1
6 3 1 2 3 2 1 2 1 2 1 3 2 4 2 5 3 6 1 2 2 2 3 1
输出 #1
2 1 2
数据范围
* $1 \le n, q \le 2\times 10^5$
* $1 \le u, v \le n$，共 $n-1$ 条，保证构成一棵树
* $1 \le c_i \le n$
* 对每个查询 $(u_i, T)$，$1 \le u_i, T \le n$
样例解释
* 视 1 为根，整棵树的颜色多重集为 {1,2,3,2,1,2}：
颜色 1 出现 2 次、颜色 2 出现 3 次、颜色 3 出现 1 次。
查询 $(1,2)$：出现次数至少为 2 的颜色有 {1,2}，共 2 种。
* 以 2 为根的区域为结点集合 {2,4,5}，颜色多重集 {2,2,1}：
查询 $(2,2)$：满足至少 2 次的只有颜色 2，答案 1。
* 以 3 为根的区域为结点集合 {3,6}，颜色多重集 {3,2}：
查询 $(3,1)$：两种颜色都至少出现 1 次，答案 2。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？