← 返回题目列表

AtCoder · pakencamp_2024_day2_c

C. 可以制作回文

中文机器翻译题面 查看原题

配点 : 100 点

問題文

帕肯王国是 它由 N 个城镇组成,每个城镇都有 它的编号为 1, 2, \ldots, N 。这些城镇是 它们由 N-1 道路连接。 它的编号为 1, 2, \ldots, N-1 。路 i (1 \leq i \leq N-1) 是一个城镇 A_i 和镇 您可以在 B_i 双向连接。从任何一个城镇到任何一个城镇 0 您可以穿越多条道路。

2 镇 a, b 的距离是 设置为移动到 a 减去 b 时要经过的最小边数。特别是, 当 a=b 时,距离为 请注意 0 。

帕肯王国的每个城镇都有一家出售信件的商店。帕肯王国的角色是 1 以上 N 用下面的整数表示, 位于 i 的商店 您只能购买 C_i 。假设各门店库存充足,不会缺货。

现在,在帕克王国,从现在开始, M 游行将持续数天。 i 当天,小镇 U_i 卡拉町 移至 V_i 最短路线的城镇(城镇) (包括 U_i, V_i )是举行游行的城镇。特别是, U_i = V_i 当游行进城时 它将仅在 U_i 举行。举行游行的城镇里的商店都开门,可以买信,但其他城镇的商店都关门了,不能买信。

您,帕肯王国的国王,想向前来观看游行的人们表示欢迎。 M 我将在几天内向人们发出指示。 居住在 i 当天,小镇 L_i, L_i+1, \ldots, R_i 的每位居民 1 向此人提供以下指示。

  • i 在当天举行游行的城镇中,在距公民居住城镇最近的城镇的商店购买一封信,并将其赠送给您。

您认为回文是最美丽的字母串,因此您想通过显示由说明提供的字母组成的回文来表达您的欢迎。 Q 整数集 给出了 (S_i, T_i) ,所以 S_i, S_i+1, \ldots, T_i 确定是否可以通过使用当天出现的所有字母并适当地重新排列它们来创建回文。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N (1 \leq i \leq N-1)
  • 从任何城镇到任何城镇 0 可以穿越多条道路。
  • 1 \leq C_i \leq N (1 \leq i \leq N)
  • 1 \leq U_i \leq V_i \leq N (1 \leq i \leq M)
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 1 \leq S_i \leq T_i \leq M (1 \leq i \leq Q)
  • 所有输入均为整数

小課題

  1. (5 点) N \leq 300, M \leq 300, Q = 1, S_1 = 1, T_1 = M, C_i \leq 2 (1 \leq i \leq N)
  2. (5 点) N \leq 2000, M \leq 2000, Q = 1, S_1 = 1, T_1 = M, C_i \leq 2 (1 \leq i \leq N)
  3. (5 点) N \leq 2000, M \leq 2000, C_i \leq 2 (1 \leq i \leq N)
  4. (5 点) A_i=i, B_i=i+1 (1 \leq i \leq N-1) ,C_i \leq 2 (1 \leq i \leq N)
  5. (20 点) A_{i+1} = B_i (1 \leq i \leq N-2) ,C_i \leq 2 (1 \leq i \leq N)
  6. (10 点) A_{i+1} = B_i (1 \leq i \leq N-2)
  7. (40 点) C_i \leq 2 (1 \leq i \leq N)
  8. (10 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
C_1 C_2 \ldots C_N
M
U_1 V_1 L_1 R_1
U_2 V_2 L_2 R_2
\vdots
U_M V_M L_M R_M
Q
S_1 T_1
S_2 T_2
\vdots
S_Q T_Q

出力

Q 行。 i 在线 i 第整数集 如果你可以为 (S_i, T_i) 创建一个回文 Yes ,如果你做不到 No 。 (12:51 修改)


入力例 1

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

出力例 1

Yes

帕肯王国如下。

另外,每天都会发生以下事件。

  • 1 日是镇 游行将在 1, 3, 5 举行。你就是那个城镇 向 2, 3, 4 的居民发出指示,每位居民将 带有 1, 3, 3 的字符 购买 1, 1, 1 。
  • 2 日是镇 游行将在 2, 1, 3, 4 举行。你就是那个城镇 向 1, 2, 3 的居民发出指示,每位居民将 带有 1, 2, 3 的字符 购买 1, 2, 1 。
  • 3 日是镇 游行将在 3 举行。你就是那个城镇 向 5 的居民发出指示,每位居民将 带有 3 的字符 购买 1 。

因此, 输出 1, 2, 3 如果您重新排列当天专用的字母, 您可以创建回文 1, 1, 1, 2, 1, 1, 1 。 满足

此输入示例是一个小作业。 1, 2, 3, 7, 8 约束。


入力例 2

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

出力例 2

No
Yes
Yes

此输入示例是一个小作业。 3, 4, 5, 6, 7, 8 约束。


入力例 3

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

出力例 3

No
Yes

此输入示例是一个小作业。 3, 5, 6, 7, 8 约束。


入力例 4

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

出力例 4

Yes
Yes
Yes
Yes
Yes

此输入示例是一个小作业。 8 约束。