E. In a Trap

Codeforces

IDCF840E

Time3000ms

Memory256MB

Difficulty—

trees

English · Original

Chinese · Translation

Formal · Original

Lech got into a tree consisting of _n_ vertices with a root in vertex number 1. At each vertex _i_ written integer _a__i_. He will not get out until he answers _q_ queries of the form _u_ _v_. Answer for the query is maximal value among all vertices _i_ on path from _u_ to _v_ including _u_ and _v_, where _dist_(_i_, _v_) is number of edges on path from _i_ to _v_. Also guaranteed that vertex _u_ is ancestor of vertex _v_. Leha's tastes are very singular: he believes that vertex is ancestor of itself. Help Leha to get out. The expression means the bitwise exclusive _OR_ to the numbers _x_ and _y_. Note that vertex _u_ is ancestor of vertex _v_ if vertex _u_ lies on the path from root to the vertex _v_. ## Input First line of input data contains two integers _n_ and _q_ (1 ≤ _n_ ≤ 5·104, 1 ≤ _q_ ≤ 150 000) — number of vertices in the tree and number of queries respectively. Next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ _n_) — numbers on vertices. Each of next _n_ - 1 lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — description of the edges in tree. Guaranteed that given graph is a tree. Each of next _q_ lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — description of queries. Guaranteed that vertex _u_ is ancestor of vertex _v_. ## Output Output _q_ lines — answers for a queries. [samples]

Lech 进入了一棵包含 #cf_span[n] 个顶点的树，根节点为第 #cf_span[1] 号顶点。每个顶点 #cf_span[i] 上写有一个整数 #cf_span[ai]。他必须回答 #cf_span[q] 个形如 #cf_span[u] #cf_span[v] 的查询后才能离开。每个查询的答案是路径从 #cf_span[u] 到 #cf_span[v]（包含 #cf_span[u] 和 #cf_span[v]）上所有顶点 #cf_span[i] 中，表达式 #cf_span[ai ⊕ dist(i, v)] 的最大值，其中 #cf_span[dist(i, v)] 表示从 #cf_span[i] 到 #cf_span[v] 的路径上的边数。题目保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。Leha 的品味非常独特：他认为一个顶点是它自身的祖先。表达式 #cf_span[x ⊕ y] 表示数字 #cf_span[x] 和 #cf_span[y] 的按位异或。注意，顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先，当且仅当 #cf_span[u] 位于从根到 #cf_span[v] 的路径上。输入数据的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 5·104]，#cf_span[1 ≤ q ≤ 150 000]），分别表示树中顶点数和查询数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n]），表示每个顶点上的数值。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述树中的一条边。保证给定图是一棵树。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述一个查询。保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。请输出 #cf_span[q] 行，每行为对应查询的答案。 ## Input 输入数据的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 5·104]，#cf_span[1 ≤ q ≤ 150 000]），分别表示树中顶点数和查询数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n]），表示每个顶点上的数值。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述树中的一条边。保证给定图是一棵树。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述一个查询。保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。 ## Output 请输出 #cf_span[q] 行，每行为对应查询的答案。 [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the number of vertices and queries, respectively. Let $ T = (V, E) $ be a rooted tree with vertex set $ V = \{1, 2, \dots, n\} $ and root at vertex $ 1 $. Let $ a: V \to \mathbb{Z} $ be a function assigning to each vertex $ i $ a value $ a_i \in [0, n] $. For any two vertices $ u, v \in V $, let $ P(u, v) $ denote the unique simple path from $ u $ to $ v $ in $ T $. Given that $ u $ is an ancestor of $ v $, $ P(u, v) $ is the path from $ u $ down to $ v $ along the tree. **Constraints** 1. $ 1 \le n \le 5 \cdot 10^4 $ 2. $ 1 \le q \le 150\,000 $ 3. $ 0 \le a_i \le n $ for all $ i \in V $ 4. The input graph is a tree with root at vertex $ 1 $. 5. For each query $ (u, v) $, $ u $ is an ancestor of $ v $ (including $ u = v $). **Objective** For each query $ (u, v) $, compute: $$ \max_{i \in P(u, v)} a_i $$ That is, the maximum value among all vertex weights on the path from $ u $ to $ v $, inclusive.

Samples

Input #1

Output #1

3
4
3

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. In a Trap",
    "description": {
      "content": "Lech got into a tree consisting of _n_ vertices with a root in vertex number 1. At each vertex _i_ written integer _a__i_. He will not get out until he answers _q_ queries of the form _u_ _v_. Answer ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF840E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Lech got into a tree consisting of _n_ vertices with a root in vertex number 1. At each vertex _i_ written integer _a__i_. He will not get out until he answers _q_ queries of the form _u_ _v_. Answer ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Lech 进入了一棵包含 #cf_span[n] 个顶点的树，根节点为第 #cf_span[1] 号顶点。每个顶点 #cf_span[i] 上写有一个整数 #cf_span[ai]。他必须回答 #cf_span[q] 个形如 #cf_span[u] #cf_span[v] 的查询后才能离开。每个查询的答案是路径从 #cf_span[u] 到 #cf_span[v]（包含 #cf_span[u] 和...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of vertices and queries, respectively.  \nLet $ T = (V, E) $ be a rooted tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and root at ve...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments