Problem 2E. 子树最大值查询

Problem 2E. 子树最大值查询

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 2E. 子树最大值查询

题目描述

现有一棵 \(n\) 点的树,每个结点有一个权值 \(w_i\),初始情况下根为 \(1\)。

定义:结点的 价值 是该结点子树中,权值最大的结点的 权值

回答 \(q\) 次询问,每次询问给出 \(u,v\),请输出:

  • 若树以 \(u\) 为根,则 \(v\) 的 价值 是多少?

输入格式

第一行两个整数 \(n, q\),表示树的结点数和询问次数。

接下来一行 \(n\) 个整数,表示结点 \(i\) 的权值。

接下来 \(n - 1\)​ 行每行两个整数,表示树的一条边。

接下来 \(q\) 行每行两个整数 \(u, v\),表示一次询问。

输出格式

对于每次询问输出一行表示答案。

样例输入1

6 4
1 2 3 4 5 6
1 3
1 6
2 6
3 4
3 5
4 1
6 3
2 4
4 4

样例输出1

6
5
4
6

样例1解释

对于第一组询问,\(3\) 的子树中结点的 权值 分别是 \(3,1,6,2\),所以最大权值为 \(6\)​。

对于第三组询问,\(4\) 的子树中结点的 权值 是 \(4\),最大权值为 \(4\)。

注意到该样例为了演示,各结点的权值等于编号,其他测试点可能不满足这一点。

image-20240421103930152

数据范围及限制

对于 \(60\%\) 的数据,\(1\le n,q\le 10^3\)。

对于 \(100\%\) 的数据,\(1\le n,q\le 5\times 10^5, 1\le w_i\le n,1\le u,v\le n\)。

2024春 悬赏令第二周

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-04-21 18:30
结束于
2024-04-28 00:00
持续时间
149.5 小时
主持人
参赛人数
58