#P13939. [2024多校联盟省选模拟]数点

    ID: 13146 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100虚树树链剖分树状数组LCA数据结构分治

[2024多校联盟省选模拟]数点

题目描述

给定一棵 nn 个点的无根树,树上每个点有一种颜色。进行 qq 次询问:对某个点 xx,询问与 xx 距离不超过 dd 的所有点中,出现过的颜色有多少种。

一个测试点中有多组测试数据。

输入格式

第一行一个整数 numnum,表示该测试点编号;若为样例则该数为 00。
第二行一个整数 TT,表示测试数据组数。

对于每组数据:

  • 第一行一个整数 nn,表示树的大小。
  • 接下来一行 nn 个整数,第 ii 个整数 cic_i 表示第 ii 个节点的颜色。
  • 接下来 n−1n-1 行每行两个整数 u,vu,v,表示树上的一条边 (u,v)(u,v)。
  • 接下来一个整数 qq,表示询问个数。
  • 接下来 qq 行每行两个整数 x,dx,d,表示询问树上与 xx 距离 ≤d\le d 的范围内出现过的颜色种数。

输出格式

对于每组数据输出 qq 行,每行一个整数,表示每个询问的答案。

0
1
5
1 2 3 1 2
1 2
1 3
2 4
2 5
5
1 1
2 0
3 1
4 2
3 2
3
1
2
2
3

数据范围与提示

  • 对于所有数据:n,q≤105n,q\le 10^5,1≤ci,ui,vi,x≤n1\le c_i,u_i,v_i,x\le n,0≤d≤n0\le d\le n,1≤T≤31\le T\le 3。
  • 对于测试点 1∼41\sim 4:n,q≤5000n,q\le 5000。
  • 对于测试点 5∼85\sim 8:ui=1u_i=1。
  • 对于测试点 9∼139\sim 13:ui=i, vi=i+1u_i=i,\ v_i=i+1。
  • 对于测试点 14∼1814\sim 18:ci=ic_i=i。
  • 对于测试点 19∼2519\sim 25:无特殊限制。