[GDKOI2023 提高组] 树

Luogu

IDLGP10107

Time4000ms

Memory1024MB

DifficultyP7

倍增2023广东树链剖分前缀和位运算差分

给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。有 $Q$ 次询问，对于一次询问，给定 $(x, k)$，设 $x$ 号结点的子树内（包含 $x$ 自身）的所有满足距离 $x$ 号结点不超过 $k$ 的结点编号为 $c_1, c_2, . . . , c_m$，则这次询问的答案为： $$(v_{c_1} ⊕ d(c_1, x)) + (v_{c_2} ⊕ d(c_2, x)) + \cdots + (v_{c_m} ⊕ d(c_m, x))$$ 其中 $d(x, y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$⊕$ 表示异或运算。 ## Input 第一行一个整数 $n$ 表示树的大小。第二行 $n$ 个整数表示 $v_i$。第三行 $n - 1$ 个整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号 $p_i$。第四行一个整数 $Q$。接下来 $Q$ 行，每行两个整数 $x, k$，表示一个 $(x, k)$ 的查询。 ## Output 输出共 $Q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。 [samples] ## Note 对于 10% 的数据，满足 $n, Q ≤ 2 \times 10^3$。对于 20% 的数据，满足 $n, Q ≤ 10^5$。对于另外 20% 的数据，满足 $p_i = i - 1$。对于另外 10% 的数据，满足 $k ≤ 20$。对于另外 20% 的数据，满足 $k = n$。对于另外 10% 的数据，满足 $v_i = 0$。对于 100% 的数据，满足 $1 ≤ n, Q ≤ 10^6$，$ 0 ≤ v ≤ 10^9$，$ 1 ≤ p_i < i$，$ 1 ≤ x, k ≤ n$。

Samples

Input #1

10
9 3 0 7 4 8 8 7 2 5
1 1 2 2 3 6 6 8 7
10
8 2
2 1
5 1
4 1
4 1
1 4
4 1
6 3
4 1
1 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2023 提高组] 树",
    "description": {
      "content": "给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。 有 $Q$ 次询问，对于一次询问，给定 $(x, k)$，设 $x$ 号结点的子树内（包含 $x$ 自身）的所有满足距离 $x$ 号结点不超过 $k$ 的结点编号为 $c_1, c_2, . . . , c_m$，则这次询问的答案为： $$(v_{c_1} ⊕ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10107"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。\n\n有 $Q$ 次询问，对于一次询问，给定 $(x, k)$，设 $x$ 号结点的子树内（包含 $x$ 自身）的所有满足距离 $x$ 号结点不超过 $k$ 的结点编号为 $c_1, c_2, . . . , c_m$，则这次询问的答案为：\n\n$$(v_{c_1} ⊕ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments