【luogu SP10707】COT2Count on a tree II（树上莫队）

题目描述

给定一棵 $n$ 个节点的树，每个节点有一个权值 $a_i$。有 $m$ 次询问，每次询问给定一个节点 $u$ 和一个整数 $k$，求树上距离 $u$ 不超过 $k$ 的节点中，权值为 $x$ 的节点个数。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示 $a_1,a_2,…,a_n$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示存在一条边 $(u,v)$。

接下来 $m$ 行，每行包含两个整数 $u,k$。

输出格式

对于每个询问，输出一个整数，表示树上距离 $u$ 不超过 $k$ 的节点中，权值为 $x$ 的节点个数。

数据范围

$1≤n,m≤10^5$,

$1≤a_i≤10^6$,

$1≤u,v≤n$,

$1≤k≤10^9$

输入样例

5 4

1 2 3 4 5

1 2

1 3

2 4

2 5

1 2

2 1

3 2

4 3

输出样例

1

1

0

0

算法1

(树上莫队) $O(m\sqrt n\log n)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码