1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <bits/stdc++.h>
const int MaxN = 100010;
struct node
{
int val, dfn, r, id;
};
struct query
{
int l, r;
int pos, id, k;
};
struct edge
{
int next, to;
};
node a[MaxN];
query q[MaxN];
edge e[MaxN << 1];
int n, m, cnt, dfscnt, size;
int head[MaxN], ans[MaxN], sum[MaxN], val[MaxN];
inline int comp(node a, node b) { return a.dfn < b.dfn; }
inline int cmp(query a, query b)
{
if (a.pos != b.pos)
return a.pos < b.pos;
return a.r < b.r;
}
inline void add_edge(int u, int v)
{
++cnt;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
inline void dfs(int u)
{
a[u].dfn = ++dfscnt;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (!a[v].dfn)
dfs(v);
}
a[u].r = dfscnt;
}
inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
inline void add(int x) { ++val[a[x].val], ++sum[val[a[x].val]]; }
inline void del(int x) { --sum[val[a[x].val]], --val[a[x].val]; }
inline void solve()
{
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{
while (l > q[i].l)
--l, add(l);
while (r < q[i].r)
++r, add(r);
while (l < q[i].l)
del(l), ++l;
while (r > q[i].r)
del(r), --r;
ans[q[i].id] = sum[q[i].k];
}
}
int main()
{
n = read(), m = read();
size = pow(n, 0.55);
for (int i = 1; i <= n; i++)
a[i].val = read(), a[i].id = i;
for (int i = 1; i <= n - 1; i++)
{
int u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}
dfs(1);
for (int i = 1; i <= m; i++)
{
int v, k;
v = read(), k = read();
q[i].l = a[v].dfn, q[i].r = a[v].r, q[i].k = k;
q[i].id = i, q[i].pos = (q[i].l - 1) / size + 1;
}
std::sort(q, q + m + 1, cmp);
std::sort(a + 1, a + n + 1, comp);
solve();
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
|