yl-9/probench huggingface dataset:
# 冰冰的异或

## 题目描述

给定一个正整数 $n$，求 $\text{mex}\\{i\oplus j\mid i\in [1,n],j\in[1,n] \\}$。  
  


此处的 $\text{mex}$ 是指集合中不存在的最小非负整数。 

  


此处的 $\oplus$ 表示按位异或运算，按位异或是一种二进制操作，它操作两个长度相等的二进制串，对每个对应的位对执行逻辑异或操作，得到一个和这两个二进制串长度相同的二进制串。如果只有一个位为 $1$，则每个位置的结果为 $1$，但如果两个位都为 $0$ 或两个位都为 $1$，则结果为 $0$。简单来说，我们对这两个二进制串的每个位分别进行比较，如果这两个二进制串某一位，它们的位上的数不同，则按位异或运算的结果这一位为 $1$，如果它们相同，则按位异或运算的结果这一位为 $0$。 

  


例如：$0010\oplus 1010=1000$。 

  


对于两个十进制数的按位异或运算，其结果为这两个数转换成二进制后进行上述按位异或运算后的结果的十进制表达。 

  


例如：十进制下 $5\oplus 3= 0101\oplus 0011=0110=6$  


## 输入描述:
    
    
    第一行一个正整数 $t(1\leq t\leq 10^5)$ 表示数据组数。  
      
    接下来 $t$ 行，每行一个正整数 $n(1\leq n\leq 10^{18})$。  
    

## 输出描述:
    
    
    共 $t$ 行，每行一个非负整数表示 $\text{mex}\{i\oplus j\}(i,j\in[1,n])$。

示例1 

## 输入
    
    
    2
    1
    3

## 输出
    
    
    1
    4


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Difficulty: 1100
# 冰冰的分界线

## 题目描述

【题目背景】

  


fresh_boy 在二维平面上有 $n$ 个朋友。  
  
这天，fresh_boy 收到了来自这 $n$ 个朋友的邀约。  
  
对于任意两个朋友 $A,B$，若 fresh_boy 到 $A$ 的距离等于到 $B$ 的距离，fresh_boy 没有理由拒绝 $A$ 或 $B$。若 fresh_boy 到 $A$ 的距离小于到 $B$ 的距离，fresh_boy 可以直接接受 $A$ 的邀约，反之，若 fresh_boy 到 $B$ 的距离小于到 $A$ 的距离，fresh_boy 可以直接接受 $B$ 的邀约，fresh_boy 不想陷入两难的抉择，所以他想要避开这些会使得 fresh_boy 到 $A,B$ 的距离相等的位置。

  


【题目描述】 

  


若 fresh_boy 某个朋友的坐标为 $(x,y)$，fresh_boy 的坐标为 $(X,Y)$，则他们之间的距离定义为：$dis=\sqrt{(x-X)^2+(y-Y)^2}$。  
  
对于任意两个朋友，由 fresh_boy 和二人距离相等的点所构成的直线称为一条分界线。  
  
现给定 fresh_boy $n$ 个朋友在二维平面上的坐标，求不同分界线的数量，两条分界线相同当且仅当其完全重合 

  


提示：计算机的浮点数在进行比较时可能会存在精度误差，存在不能精确表示实数的情况。  


## 输入描述:
    
    
    多组测试数据。  
      
    第一行一个正整数 $t(1\leq t\leq 10)$ 表示测试数据组数。  
      
    对于每组测试数据共三行。  
      
    第一行一个正整数 $n(2\leq  \sum n\leq 1000)$ 表示 fresh_boy 朋友数量。第二行 $n$ 个整数表示 fresh_boy 朋友的 $x(|x|\leq 10^5)$ 坐标；第三行 $n$ 个整数表示 fresh_boy 朋友的 $y(|y|\leq 10^5)$ 坐标。  
      
    数据保证 fresh_boy 没有两个朋友的坐标相同。

## 输出描述:
    
    
    共 $t$ 行，每行一个正整数表示不同的分界线数量。

示例1 

## 输入
    
    
    3
    6
    -2 44 -17 42 -12 12
    9 -43 -14 -30 7 -10
    3
    -32 -45 31
    -3 17 -16
    4
    1 3 4 6
    0 0 0 0

## 输出
    
    
    15
    3
    5


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Difficulty: 1600
# 冰冰的 GCD

## 题目描述

给定三个排列 $a,b,c$，$m$ 次询问一个 $x$，求 $g(f(x))$。  
  
对于 $f(x)$，若排列 $b$ 中第 $x$ 个元素之后不存在满足 $\gcd(b_i,b_x)\neq 1$ 的 $b_i$（$i>x$），则 $f(x)=b_x$。 反之 $f(x)$ 的值为排列 $b$ 中第 $x$ 个元素之后第一个满足 $\gcd(b_i,b_x)\neq 1$ 的 $\gcd(b_x,b_i)$。  
  
对于 $g(x)$，$g(x)=\sum\limits_{i=c[x]}^n[x\mid a_i]$。  
  
其中 $[a\mid b]=\begin{cases}1&& a\mid b\\\0 && a\nmid b\end{cases}$，$a\mid b$ 表示 $b$ 是 $a$ 倍数，$a\nmid b$ 表示 $b$ 不是 $a$ 的倍数。  
  
长度为 $n$ 的排列是一个由 $n$ 个不同整数组成的数组，这些整数从 $1$ 到 $n$ 以任意顺序排列。

## 输入描述:
    
    
    第一行输入两个正整数 $n,m(1\le n,m\le 10^5)$ 分别表示排列大小和询问次数。  
      
    第二行 $n$ 个正整数表示排列 $a$。  
      
    第三行 $n$ 个正整数表示排列 $b$。  
      
    第四行 $n$ 个正整数表示排列 $c$。  
      
    接下来 $m$ 行，每行一个正整数 $x(1\le x\le n)$ 表示询问。

## 输出描述:
    
    
    输出共 $m$ 行，对于每次询问输出一行一个整数表示结果。

示例1 

## 输入
    
    
    5 5
    5 3 4 2 1
    5 1 3 2 4
    3 4 5 1 2
    2
    1
    4
    5
    3

## 输出
    
    
    3
    0
    1
    1
    0


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Difficulty: 1900
# 序列中的排列

## 题目描述

给定一个长度为 $n$ 的序列，问它是否存在一个子序列，使得这个子序列是一个 $k$ 的排列。  
  
某个序列的**子序列** 是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。  
  
一个 $k$ 的排列是一个长度为 $k$ 的整数序列，其中包含了从 $1$ 到 $k$ 的每个数字，每个数字仅出现一次。例如， $(1) , (4, 3, 5, 1, 2) ,(3, 2, 1)$ 是排列，而 $(1, 1) , (4, 3, 1) , (2, 3, 4)$ 不是。

## 输入描述:
    
    
    第一行包含一个 $T(1\le T\le 100)$，表示测试用例组数。  
      
    每个测试用例第一行包含两个整数 $n,k(1\le n\le 100,1\le k\le 100)$。  
      
    第二行包含 $n$ 个用空格分隔的整数 $a_i(1\le a_i\le 100)$，表示给定的序列。

## 输出描述:
    
    
    对于每个测试用例，假如给定序列中存在一个子序列，使得这个子序列是一个长度为 $k$ 的排列，输出 $YES$，否则输出 $NO$。

示例1 

## 输入
    
    
    5
    5 4
    1 2 4 5 3
    5 6
    1 2 3 4 100
    5 5
    1 2 3 5 6
    3 2
    1 3 3
    1 1
    1

## 输出
    
    
    YES
    NO
    NO
    NO
    YES

## 说明
    
    
    对于第一组测试用例，输入的序列包含一个子序列 (1,2,4,3)，是一个 4 的排列。
    
    对于第二组测试用例，输入的序列没有一个子序列是 6 的排列。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 模拟
Difficulty: 600
# 连分数

## 题目描述

给定 $a$，定义  
$x = a + \cfrac{1}{a + \cfrac{1}{a + \cfrac{1}{a + ...}}}$  
求 $x$ 的值。  
  
形式上说，设 $f(n) = \left\\{\begin{matrix} a & n=1\\\ a+\frac {1}{f(n-1)} & n>1 \end{matrix}\right.$，$x=\lim_{n \to + \infty}f(n)$，求 $x$ 的值。

## 输入描述:
    
    
    第一行包含一个 $T(1\le T\le 10^5)$，表示测试用例组数。  
      
    随后每一行一个浮点数 $a(0< a\le 10^5 )$，小数点后位数不超过 $2$ 位。

## 输出描述:
    
    
    对于每个测试数据，输出一行，包含一个浮点数，表示答案，如果答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案正确。  
      
    形式上，假设你的答案为 $x$，标准答案为 $y$。当且仅当 $\frac{|x-y|}{max(1,|y|)}\leq 10^{-9}$ 时，你的答案被认为是正确的。

示例1 

## 输入
    
    
    5
    6.78
    0.01
    100.00
    2.00
    100000.00

## 输出
    
    
    6.924416500640523
    1.005012499921876
    100.009999000199950
    2.414213562373095
    100000.000010000000003


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

Tags: 数学
Difficulty: 1000
# sum

## 题目描述

有 $n$ 个数 $a_i$，你可以进行若干次修改操作，每一次操作任意修改一个数的值为 $x(-10^4\le x\le 10^4)$。  
  
问最少多少次操作使得这 $n$ 个数的和为 $sum$。

## 输入描述:
    
    
    第一行输入一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。接下来是 $T$ 个测试用例。  
      
    每个测试用例第一行包含两个整数 $n,sum(1\le n\le 2\times  10^5,-n\times10^4\le sum\le n\times 10^4)$。  
      
    每个测试用例第二行包含 $n$ 个整数 $a_i(-10^4\le a_i\le 10^4)$。  
      
    保证所有测试用例 $n$ 的和不超过 $2\times 10^5$。

## 输出描述:
    
    
    对于每个测试用例，输出一行，包含一个整数，表示答案。  
      
    可以证明，在数据范围的限制下，一定有一种操作方案满足条件。

示例1 

## 输入
    
    
    1
    4 10
    1 2 3 5

## 输出
    
    
    1

## 说明
    
    
    将 $5$ 修改为 $4$，然后 $1+2+3+4=10$，符合题意，所以修改一次即可将这 $n$ 个数的和修改为 $10$，可以证明，没有更优的操作次数。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 图论, 最短路
Difficulty: 1000
# 最短？路径

## 题目描述

给定一个 $n$ 个点 $m$ 条边的无向图，LH 打算从点 $1$ 出发去点 $n$。  
  
假如 LH 到达了一个点 $i$，那么他可以选择在这个点花费 $a_i$ 的时间休息后继续赶路，或者不休息然后花费 $1$ 的时间简单整顿后继续赶路。  
  


LH 不能连续超过 $k$ 个节点不休息，问从 $1$ 到 $n$ 的最短时间。 

  


注意：假如 LH 到达了点 $n$ 也需要选择休息或者不休息。  


## 输入描述:
    
    
    第一行输入一个整数 $T(1\le T\le 10^4)$，表示测试用例组数。接下来是 $T$ 个测试用例。  
      
    每个测试用例第一行包含三个整数 $n,m,k(2\le n\le 2\times 10^5,1\le m\le 3\times 10^5,0\le k\le 10)$。   
      
    第二行输入 $n$ 个整数 $a_i(0\le a_i\le 10^9)$，表示在第 $i$ 个点休息需要花费的时间。  
      
    随后 $m$ 行每行两个整数 $u ,v$，表示 $u$ 和 $v$ 之间有一条无向边。  
      
    
    
    保证输入的图联通，没有重边和自环。
    
      
    
    
    保证所有测试用例 $n$ 的和不超过 $2\times 10^5$，$m$ 的和不超过 $3\times 10^5$。  
    

## 输出描述:
    
    
    对于每个测试用例，输出一个整数，表示 LH 从 $1$ 到 $n$ 的最短时间。

示例1 

## 输入
    
    
    1
    5 6 2
    7 7 3 6 4
    4 5
    1 3
    3 4
    5 2
    2 4
    1 4

## 输出
    
    
    6

## 说明
    
    
    一种可能的最优方案为 $1->4->5$。  
      
    其中点 $1$ 和点 $4$ 不休息，在点 $5$ 休息，总时间为 $1+1+a_5=6$。

示例2 

## 输入
    
    
    2
    20 30 8
    9 10 2 8 1 6 7 10 6 10 7 0 0 3 4 0 7 9 4 3
    18 4
    8 10
    17 6
    11 3
    7 4
    7 14
    3 8
    10 19
    16 8
    11 4
    13 14
    17 14
    4 15
    12 5
    12 17
    16 9
    5 20
    7 2
    1 4
    10 5
    14 15
    3 5
    17 8
    16 6
    9 10
    16 17
    4 2
    17 20
    10 7
    16 1
    20 30 3
    2 0 2 2 9 6 7 2 5 3 7 1 8 8 8 3 1 0 8 9
    1 17
    11 8
    17 16
    14 19
    7 6
    3 4
    10 15
    4 9
    14 18
    20 5
    7 8
    18 10
    3 6
    7 1
    5 14
    13 5
    14 3
    15 2
    12 13
    7 3
    6 18
    2 10
    9 3
    1 14
    11 4
    3 17
    14 10
    7 14
    13 8
    6 5

## 输出
    
    
    3
    5


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 动态规划
Difficulty: 1700
# k - 路径（easy vension）

## 题目描述

********这是问题的简单版本。三个版本的做法****之间**** 可能有交集。****  


  


给定一颗 $n$ 个点的无根树，每个节点有类型和权值，分别用 $c$ 和 $w$ 表示。一条简单路径的权值为这条路径包含的节点权值之和。 

  
假设一条简单路径至少经过一个类型为 $k$ 的节点，那么这条路径是 $k$ - 路径。  
  


对于所有的 $k=1,2,3,...n$，输出一个整数，表示所有 $k$ - 路径的最大权值，假如不存在，输出 $-1$。 

  


提示：本题输入输出数据量较大，建议选手使用快速的输入输出方式。  


## 输入描述:
    
    
    第一行输入一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。接下来是 $T$ 个测试用例。  
      
    每个测试用例第一行输入一个整数 $n(1\le n\le 10^6)$。  
      
    第二行有 $n$ 个数 $c_i(1\le c_i \le n)$，表示每个节点的类型。  
      
    第三行有 $n$ 个数 $w_i(-10^9\le w_i\le 10^9)$，表示每个节点的权值。  
      
    
    
    然后 $n-1$ 行，每一行有两个整数 $u,v$，表示有一条 $u$ 到 $v$ 的无向边。
    
      
    
    
    保证所有测试用例 $n$ 的和不超过 $10^6$。  
    

## 输出描述:
    
    
    对于每个测试用例，输出一行，包含 $n$ 个空格分隔的整数，表示答案。

示例1 

## 输入
    
    
    3
    2
    1 1
    -8 5
    2 1
    5
    5 1 3 4 1
    6 6 6 9 10
    3 1
    4 3
    1 5
    2 1
    4
    1 4 1 3
    -2 -9 8 10
    2 1
    1 3
    4 1

## 输出
    
    
    5 -1
    31 -1 31 31 31
    16 -1 16 -1

## 说明
    
    
    在第一个测试用例中，简单路径 $(2,2)$ 包含类型为 $1$ 的节点，所以是一条 $1$ - 路径，权值为 $5$。简单路径 $(1,2)$ 也包含类型为 $1$ 的节点，权值为 $-3$。取最大，所以对于 $k=1$，输出 $5$。对于 $k=2$，没有一条路径是 $2$ -路径，所以输出 $-1$。  
      
    在第二个测试用例中，对于 $k=1$，简单路径 $(4,5)$ 包含类型为 $1$ 的节点，所以是一条 $1$ - 路径，权值为$31$，显然，没有其它任何一条 $1$ - 路径比这条路径权值更大。

示例2 

## 输入
    
    
    6
    10
    6 8 10 6 4 3 10 2 7 6
    -10 5 -10 8 -5 7 -1 -7 3 2
    10 3
    8 1
    8 6
    5 6
    2 9
    2 10
    9 7
    7 1
    9 4
    10
    10 9 8 4 1 8 4 5 1 9
    -1 -9 -10 -10 1 -6 9 -8 -1 -9
    9 2
    3 8
    2 6
    10 6
    4 7
    2 3
    5 2
    1 6
    7 3
    10
    5 3 1 1 1 5 9 10 8 5
    -4 -3 4 -10 -3 -3 -2 1 -2 7
    6 2
    2 10
    8 5
    3 7
    10 5
    6 1
    4 7
    4 5
    9 1
    10
    3 7 8 3 6 8 3 10 9 10
    5 -5 8 -9 5 5 -8 3 -6 2
    2 1
    7 2
    9 3
    6 8
    6 4
    10 1
    3 2
    9 8
    8 5
    10
    3 7 8 3 6 8 3 10 9 10
    5 -5 8 -9 5 5 -8 3 -6 2
    2 1
    7 2
    9 3
    6 8
    6 4
    10 1
    3 2
    9 8
    8 5
    5
    4 2 5 4 2
    4 3 -2 -1 -3
    3 1
    3 2
    3 5
    4 1

## 输出
    
    
    -1 0 7 2 -1 18 18 18 -1 10
    1 -1 -1 9 -8 -1 -1 -1 -8 -1
    5 -1 4 -1 7 -1 -1 -2 2 5
    -1 -1 12 -1 -1 13 12 13 12 13
    -1 -1 12 -1 -1 13 12 13 12 13
    -1 5 -1 5 5


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数据结构, 树, 动态规划, 树形dp
Difficulty: 1900
# k - 路径（mid vension）

## 题目描述

********这是问题的中等版本。三个版本的做法****之间**** 可能有交集。****

  


给定一颗 $n$ 个点的无根树，每个节点有类型和权值，分别用 $c$ 和 $w$ 表示。一条简单路径的权值为这条路径包含的节点权值之和。 

  
对于一个长度为 $len+1(len>1)$ 的序列 $a$，假如 $a_1=a_{len+1}=len$，并且 $a_2,a_3,...,a_{len}$ 是一个长度为 $len-1$ 的排列，那么称序列 $a$ 是 $len$ - 特殊排列。  
  
假如从 $u$ 走到 $v$ 长度为 $k+1$ 的简单路径依次经过的节点类型组成的序列是一个 $k$ - 特殊排列，那么这个简单路径是一条 $k$ - 路径。  
  
**特别的** ，假如一条简单路径只由两个类型为 $1$ 的节点组成，那么这条路径是 $1$- 路径。  
  


对于 $k=1,2,3,...n$，输出一个整数，表示所有**经过** 点 $x$ 的 $k$ - 路径的最大权值，假如不存在，输出 $-1$。 

  


提示：本题输入输出数据量较大，建议选手使用快速的输入输出方式。  


## 输入描述:
    
    
    第一行输入一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。接下来是 $T$ 个测试用例。  
      
    每个测试用例第一行输入两个整数 $n,x(2\le n\le 10^6,1\le x\le n)$。  
      
    第二行有 $n$ 个数 $c_i(1\le c_i \le n)$，表示每个节点的类型。  
      
    第三行有 $n$ 个数 $w_i(-10^9\le w_i\le 10^9)$，表示每个节点的权值。  
      
    
    
    然后 $n-1$ 行，每一行有两个整数 $u,v(1\le u,v\le n)$，表示有一条 $u$ 到 $v$ 的无向边。
    
      
    
    
    保证所有测试用例 $n$ 的和不超过 $10^6$。  
    

## 输出描述:
    
    
    对于每个测试用例，输出一行，包含 $n$ 个空格分隔的整数，表示答案。

示例1 

## 输入
    
    
    1
    8 1
    1 2 3 4 2 2 4 3
    7 -8 -5 4 10 1 -7 -9
    1 2
    2 3
    3 4
    1 7
    1 5
    1 6
    1 8

## 输出
    
    
    -1 18 -15 -9 -1 -1 -1 -1

## 说明
    
    
    在第一个测试用例中，简单路径 $(5,6)$ 的权值为 $18$，并且这条简单路径的节点类型组成的序列为 $[2,1,2]$ 是一个 $2$ - 特殊排列，所以这条简单路径是一个 $2$ - 路径，并且显然没有其它任何一条 $2$ - 路径的权值比这条路径的权值大，所以对于 $k=2$，输出 $18$。

示例2 

## 输入
    
    
    4
    10 1
    1 2 3 4 5 2 3 4 1 5
    -5 9 7 8 3 -7 -10 -7 6 -1
    1 2
    2 3
    3 4
    4 5
    10 9
    1 6
    1 7
    1 10
    1 8
    10 1
    1 2 3 4 5 5 3 2 4 2
    -2 6 -1 4 10 3 4 -1 3 5
    1 2
    2 3
    3 4
    4 5
    1 8
    10 7
    1 9
    9 6
    1 10
    10 1
    1 2 3 4 5 4 5 5 5 2
    -1 -6 -3 7 8 8 5 9 -9 -5
    1 2
    2 3
    3 4
    4 5
    1 10
    7 9
    1 6
    1 9
    1 8
    10 1
    1 2 3 4 5 5 2 5 5 3
    -9 -9 6 -3 3 -9 9 -1 -3 -6
    1 2
    2 3
    3 4
    4 5
    1 8
    1 7
    9 10
    1 6
    1 10

## 输出
    
    
    -1 -3 1 12 21 -1 -1 -1 -1 -1
    -1 9 -1 10 -1 -1 -1 -1 -1 -1
    -1 -12 -1 5 14 -1 -1 -1 -1 -1
    -1 -9 -18 -1 -13 -1 -1 -1 -1 -1


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 数据结构, 树, 哈希
Difficulty: 2200
# k - 路径（hard vension）

## 题目描述

**这是问题的困难版本。三个版本的做法**之间** 可能有交集。**  


**  
**

给定一颗 $n$ 个点的无根树，每个节点有类型和权值，分别用 $c$ 和 $w$ 表示。一条简单路径的权值为这条路径包含的节点权值之和。 

  
对于一个长度为 $len+1(len>1)$ 的序列 $a$，假如 $a_1=a_{len+1}=len$，并且 $a_2,a_3,...,a_{len}$ 是一个长度为 $len-1$ 的排列，那么称序列 $a$ 是 $len$ - 特殊排列。  
  
假如从 $u$ 走到 $v$ 长度为 $k+1$ 的简单路径依次经过的节点类型组成的序列是一个 $k$ - 特殊排列，那么这个简单路径是一条 $k$ - 路径。  
  
**特别的** ，假如一条简单路径只由两个类型为 $1$ 的节点组成，那么这条路径是 $1$- 路径  
  
对于 $k=1,2,3,...n$，输出一个整数，表示所有的 $k$ - 路径的最大权值，假如不存在，输出 $-1$。  
  
提示：本题输入输出数据量较大，建议选手使用快速的输入输出方式。

## 输入描述:
    
    
    第一行输入一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。接下来是 $T$ 个测试用例。  
      
    每个测试用例第一行输入两个整数 $n(2\le n\le 2\times 10^5)$。  
      
    第二行有 $n$ 个数 $c_i(1\le c_i \le n)$，表示每个节点的类型。  
      
    第三行有 $n$ 个数 $w_i(-10^9\le w_i\le 10^9)$，表示每个节点的权值。  
      
    然后 $n-1$ 行，每一行有两个整数 $u,v(1\le u,v\le n)$，表示有一条 $u$ 到 $v$ 的无向边。  
      
    保证所有测试用例 $n$ 的和不超过 $10^6$。

## 输出描述:
    
    
    对于每个测试用例，输出一行，包含 $n$ 个空格分隔的整数，表示答案。

示例1 

## 输入
    
    
    1
    5
    1 2 1 2 2
    1 -2 5 6 -7
    2 3
    3 5
    3 4
    1 5

## 输出
    
    
    -1 9 -1 -1 -1

## 说明
    
    
    在第一个测试用例中，可能存在的 $2$ - 路径有 $(2,5)、(4,5)、(4,2)$，路径 $(2,5)$ 的权值为 $-4$，路径 $(4,5)$ 的权值为 $5$，路径 $(4,2)$ 的权值为 $9$，取最大，所以对于 $2$ - 路径，输出 $9$。

示例2 

## 输入
    
    
    1
    9
    1 3 2 4 3 4 1 4 4
    1 2 3 4 5 6 6 7 8
    1 2
    1 3
    1 7
    1 8
    2 4
    3 5
    3 6
    5 9

## 输出
    
    
    7 -1 11 24 -1 -1 -1 -1 -1


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 数据结构, 树, 树分治, 分治
Difficulty: 2200
# tb的区间问题

## 题目描述

tb 给了 fc 一个长度为 $n$ 的数组 $A$ , fc 对 $A$ 进行 $k$ 次如下操作：  
  
删除数组第一个元素或者删除数组最后一个元素。  
  
求最后得到的数组和的最大值。

## 输入描述:
    
    
    第一行输入两个正整数 $n,k(1 \le k \le n \le 5 \times 10^3)$ ，分别表示数组长度，以及操作次数。  
      
    第二行输入 $n$ 个整数表示 $A$ 数组，第 $i$ 个数为 $a_i(0 \le a_i \le 10^9)$。

## 输出描述:
    
    
    一个非负整数，表示最后得到数组和的最大值。

示例1 

## 输入
    
    
    5 4
    8 13 7 8 6

## 输出
    
    
    13


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 模拟, 枚举
Difficulty: 800
# tb的字符串问题

## 题目描述

tb 给了 fc 一个字符串。  
  
fc 对字符串可以进行若干次 （可能是0） 次如下操作：  
  
选择子串 ''$fc$'' 或者子串 ''$tb$'' ，将其从字符串中删去。  
  
求最后剩下字符串的最短长度。  


  


子串：原字符串中下标连续的一段字符串。 

## 输入描述:
    
    
    第一行输入一个正整数 $n(1\le n \le 10^6)$ ，表示字符串长度。  
    第二行输入一个长度为 $n$ 的字符串。

## 输出描述:
    
    
    一个非负整数，表示操作后的字符串的最短长度。

示例1 

## 输入
    
    
    10
    ftbfccfacb

## 输出
    
    
    4


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数据结构, 栈
Difficulty: 900
# tb的路径问题

## 题目描述

tb 给了 fc 一张有 $n \times n$ 个格点的图。  
  
图上每个格点都写着一个数。第 $i$ 行第 $j$ 列的格点上写着的数字为 $i$ 和 $j$ 的最大公约数。  
  
现在 fc 需要从第 $1$ 行第 $1$ 列出发，去往第 $n$ 行第 $n$ 列处的格点，fc 可以消耗一点能量移向相邻的格点。  
  
在任何时候，设 fc 所位于的格点上所写的数字为 $x$ ，**如果** $x$**不为** $1$ ，他可以使用传送阵传送到任何数字为 $x$ 的格点，此操作不消耗能量。  
  


求 fc 到达第 $n$ 行第 $n$ 列所消耗的最少能量。 

  


相邻：如果用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的位置，$(x,y)$ 与 $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$ 相邻。 

## 输入描述:
    
    
    一个正整数，表示 $n(1 \le n \le 10^6)$ 。

## 输出描述:
    
    
    一个非负整数，表示最少能量。

示例1 

## 输入
    
    
    2

## 输出
    
    
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 思维
Difficulty: 1100
# tb的平方问题

## 题目描述

tb 给了 fc 一个数组 A 。  
  
随后， tb 对 fc 进行了 $q$ 次询问，每次询问 tb 给 fc 一个 $x$ ，需要 fc 给出包含了 $x$ 位置且区间和为完全平方数的连续子数组个数。  
  
完全平方数：存在正整数 $t$ ，满足 $t \times t = x$ ，则称 $x$ 为完全平方数。  
  
连续子数组：原数组中某段下标连续的元素按原顺序构成的数组。

## 输入描述:
    
    
    第一行输入两个正整数 $n,q(1 \le n \le 10^3,1 \le q \le 3*10^5)$ ，表示数组长度与询问个数。  
      
    第二行输入一个长为 $n$ 的数组，表示 $A$ , 第 $i$ 个位置为 $a_i(1\le a_i\le 10^5)$ 。  
      
    接下来 $q$ 行每行输入一个正整数 $x(1 \le x \le n)$ ，表示询问的位置。

## 输出描述:
    
    
    $q$ 行，每行一个非负整数，表示符合条件的区间数。

示例1 

## 输入
    
    
    5 2
    1 2 3 4 5
    2
    4

## 输出
    
    
    1
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 差分, 枚举, 数论
Difficulty: 1200
# tb的数数问题

## 题目描述

tb 给了 fc 一个包含若干个数字的可重集合 $A$ ，如果我们说一个数字 $x$ 是好的当且仅当 $\forall \ d | x$ ，有 $d \in A$。  
  
现在，fc 想知道有多少个**不同的正整数** 是好的，请你告诉他吧。  
  


$d|x$ : 表示 $d$ 为 $x$ 的约数。 

  


$\forall \ d | x$ ，有 $d \in A$ ： $x$ 的任何约数都至少在 $A$ 中出现一次。

## 输入描述:
    
    
    第一行输入一个正整数 $n(1 \le n \le 10^6)$ ，表示集合的大小。  
      
    第二行输入 $n$ 个数，表示集合 $A$ 中的元素 $a_i(1 \le a_i \le 10^6)$ 。

## 输出描述:
    
    
    一个非负整数，表示好的数的个数。

示例1 

## 输入
    
    
    7
    1 4 3 8 10 8 9

## 输出
    
    
    3

## 备注:
    
    
    样例 $1$ 解释：  
    符合条件的正整数有 $1,3,9$ ，由于 $2$ 不在 $A$ 中，其它数又都是 $2$ 的倍数，所以其它数均不符合条件。  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 筛法, 数论, 暴力
Difficulty: 1500
# tb的排列问题

## 题目描述

tb 给了 fc 一个长度为 $n$ 的排列 $A$ ，fc 想要更改一下此排列，他选择了一个幸运数字 $w$ ,依照如下方式操作了 $n$ 次:  
  
第 $i$ 次操作中，选择两个整数 $x,y$，满足 $i \le x \le y \le min(i+w,n)$ ，交换 $A_x$ 与 $A_y$ 的值，$x$ = $y$ 时数组不变。  
  
经过这 $n$ 次操作后，他得到了新的排列 $B$ 。  
  
由于 fc 的记忆只有七秒，他很快就忘记了 $A$ 排列是什么样子，只记得一部分 $A$ 排列中的元素以及其对应位置。现在他将 $B$ 排列以及残缺的 $A$ 排列给出，请你帮他计算一下一共有多少种可能的 $A$ 排列。（可能存在 fc 记忆错乱了，没有符合条件的 $A$ 。）  
  
由于答案过大，输出方案数模以 $998244353$ 即可。  
  
排列：一个长度为 $n$ 的正整数数组，其中元素两两不同且最大值为 $n$ 。

## 输入描述:
    
    
    第一行输入 $T(1 \le T \le 10^4)$ ,表示数据的组数。  
      
    每组数据以如下格式给出：  
      
    第一行输入两个正整数$n(1 \le n \le 2 \times 10^5),w(1 \le w < n)$。  
      
    第二行输入 $n$ 个整数表示残缺的 $A_i$ ，若 $A_i = -1$ ，则表示记不清该位置上的数了，否则其为该位置上对应的数。  
      
    第三行输入 $n$ 个整数，表示一个长度为 $n$ 的排列 $B$ 。  
      
    数据保证 $\sum_{i=1}^{T} n \le 2 \times 10^5$ 。

## 输出描述:
    
    
    每组数据输出一个非负整数，表示符合条件的排列数对 $998244353$ 取模后的值。

示例1 

## 输入
    
    
    6
    3 1
    3 -1 -1
    2 1 3
    3 2
    3 -1 -1
    2 1 3
    4 1
    4 3 1 2
    1 4 3 2
    6 4
    6 1 5 -1 3 -1
    4 2 6 3 1 5
    7 4
    2 5 -1 -1 -1 4 -1
    1 3 6 2 7 4 5
    14 13
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    1 2 3 4 5 6 7 8 9 10 11 12 13 14

## 输出
    
    
    1
    2
    0
    1
    12
    331032489


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数据结构, 树状数组, 枚举, 前缀和
Difficulty: 2100
# ACM中的A题

## 题目描述

你有三根长度分别为 $a, b, c$ 的木棒 

现在必须选择将其中一根木棒，将其长度修改为原来的两倍 

那么有没有可能仅用修改后的三根木棒组成一个三角形 ?

## 输入描述:
    
    
    输入三个正整数 $a, b, c$ 表示三根木棒的长度
    
    $1 \le a, b, c \le  2× 10^9$  
    

## 输出描述:
    
    
    如果有可能组成三角形，输出 "$Yes$"
    
    否则输出 "$No$"

示例1 

## 输入
    
    
    1 2 3

## 输出
    
    
    Yes

## 说明
    
    
    将第一根木棒长度翻倍后，三根木棒长度为 2,2,3
    
    可以组成三角形

示例2 

## 输入
    
    
    3 4 5

## 输出
    
    
    Yes

示例3 

## 输入
    
    
    2 3 100

## 输出
    
    
    No

示例4 

## 输入
    
    
    1 1 3

## 输出
    
    
    No

## 备注:
    
    
    所以，什么是三角形呢 ?


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 暴力
Difficulty: 600
# ACM中的C题

## 题目描述

**此题为 $C$ 题的简单版本** ，与 $C$ 题有是否排序、交换元素限制以及数据范围的不同 

  


有一个长度为 $n$ 的数组 $\\{a_i\\}$ 

已知 $\\{a_i\\}$ 无相同元素且已经**从小到大排序**

你可以多次交换任何**相邻位置** 的2个元素  
直到每个位置的元素和原来都不相同  
若有解请输出最小交换次数，反之无解输出 -1 

  


## 输入描述:
    
    
    第一行输入一个正整数 $n$  
    第二行输入 $n$ 个非负整数 $\{a_i\}​$  
    $1\le n\le 2× 10^5; ~0\le a_i\le 2× 10^9$  
    数据保证 $a_i$ 从小到大排列且无相同 $a_i$  
    

## 输出描述:
    
    
    一个整数表示结果  
    若有解，输出最小交换次数  
    反之，输出 -1  
    

示例1 

## 输入
    
    
    2
    1 2

## 输出
    
    
    1

## 说明
    
    
    交换第一和第二个元素  
    新数组变为 [2, 1]  
    显然一次交换后即可与原数组每一位均不相同

示例2 

## 输入
    
    
    4
    0 1 2 4

## 输出
    
    
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 数学
Difficulty: 600
# ACM中的M题

## 题目描述

$\textbf{}$**此题为 $B$ 题的困难版本** ，与 $B$ 题有是否排序、交换元素限制以及数据范围的不同 

  


有一个长度为 $n$ 的数组 $\\{a_i\\}$，每个 $\\{a_i\\}$ 属于且仅属于一个类别 $\\{b_i\\}$ 

已知 $\\{a_i\\}$ 无相同元素 

你可以多次交换同一个类别下**任意** 2个元素  
直到每个位置的元素和原来都不相同  
若有解请输出最小交换次数，反之无解输出 -1

## 输入描述:
    
    
    第一行输入一个正整数 $n$  
    
    
    第二行输入 $n$ 个非负整数 $\{a_i\}​$
    
    第三行输入 $n$ 个非负整数 $\{b_i\}​$ ，表示  $\{a_i\}​$ 类别
    
    $1\le n\le 2× 10^5;~0\le a_i\le 2× 10^9 ;~0\le b_i\le 2× 10^9$  
    数据保证无相同 $a_i$

## 输出描述:
    
    
    一个整数表示结果  
    若有解，输出最小交换次数  
    反之，输出 -1

示例1 

## 输入
    
    
    3
    1 2 3
    1 1 1

## 输出
    
    
    2

## 说明
    
    
    显然3个元素属于统一类别
    
    第一次交换第一第二位置变为 [2,1,3]
    
    第二次交换第一第三位置变为 [3,1,2]
    
    显然无更少的交换次数能满足条件  
    

示例2 

## 输入
    
    
    3
    0 1 2
    0 1 2

## 输出
    
    
    -1

## 说明
    
    
    显然3个数类别均不相同不可交换

示例3 

## 输入
    
    
    4
    0 1 2 3
    0 2 2 0

## 输出
    
    
    2

示例4 

## 输入
    
    
    2
    1 2
    0 0

## 输出
    
    
    1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 模拟
Difficulty: 800
# ACM中的AC题

## 题目描述

众所周知，出题人没玩过双人成行，所以出了这道题 

你一觉醒来，发现你和另一个时空的你被困在 $n*m$ 大小矩形孤岛的 $(x, y)$ 地块上 

在地图中最多包含 平地，陷阱和传送门 三种不同地块 

你和另外一个时空的你都可以上下左右移动到相邻的地块中 

可是你和外一个时空的你只能同时以**相反的方向移动**

两人均不能跨过边界，即到达孤岛外的地方；任意人到达陷阱处会立刻死亡

  


现在，你能否给出一个移动序列，使得两人**均能** 从传送门离开，其中任意一人到达传送门后一定会离开且不会再回到该孤岛中; 

如果有，请输出该序列的最短长度、反之输出 -1 

## 输入描述:
    
    
    第一行四个正整数 $n, m, x, y$
    
    接下来 $n$ 行，每行一个长度为 $m$ 的字符串
    
      
    
    
    $1\le n,m\le 2× 10^3; ~1\le x\le n; ~1\le y\le m$
    
    数据保证
    
    字符串仅包含 .#@ 三种字符 .(平地) #(陷阱) @(传送门)
    
    保证 $(x, y)$ 位置是平地.

## 输出描述:
    
    
    输出一个整数
    
    若能离开，请请输出该序列的最短长度
    
    反之输出 -1

示例1 

## 输入
    
    
    3 3 2 2
    @.@
    #..
    @.@

## 输出
    
    
    2

## 说明
    
    
    你可以先往上后往左到达(1,1)传送门
    
    另外一个时空的你会先下后右到达(3,3)传送门

示例2 

## 输入
    
    
    1 3 1 2
    ..@

## 输出
    
    
    3

示例3 

## 输入
    
    
    3 1 2 1
    #
    .
    @

## 输出
    
    
    -1

## 说明
    
    
    显然，谁都不想走到陷阱那 ...

## 备注:
    
    
    本题输入较大，建议使用较快语言和较快的输入


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

Tags: 图论, 最短路
Difficulty: 1700
# ACM中的CM题

## 题目描述

现在在你前面有 $n$ 个地雷 

刚刚学会瞬移的你决定排走所有地雷 

遗憾的是，你的初始排雷能力 $m = 0$，但你知道 

当排雷能力为 $m$ 时，你可以任何时刻在当前位置 $l$ 处将$[l, l+m]$ 中的雷全部排走 

也可以在任何时刻任何地点，将排雷能力从 $m$ 变为 $m+1$ 

以上两种操作都需要花费 1 的时间，但瞬移不花费时间！ 

求排所有雷所需最小时间！ 

## 输入描述:
    
    
    第一行输入整数 $n$ 
    
    第二行输入 $n$ 个整数 $a_i$，表示 $n$ 个雷的位置
    
      
    
    
    $1\le n\le 2× 10^5;~1\le a_i\le 2× 10^5$  
    

## 输出描述:
    
    
    一个整数，表示排所有雷所需最短时间 

示例1 

## 输入
    
    
    3
    1 1 2

## 输出
    
    
    2

## 说明
    
    
    瞬移到1处排 [1, 1]的2个雷
    
    瞬移到2处排 [2, 2]的1个雷  
    

示例2 

## 输入
    
    
    4
    1 2 4 5

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 暴力
Difficulty: 1400
# ACM中的ACM题

## 题目描述

无聊的你回想起了$A$ 题的三角形，于是你想到了一个新的问题： 

在一个连通图中，任何一条边都属于一个集合 

如果两条边 $a,b$ 属于同一个集合当且仅当满足以下条件之一 

1\. $a,b$ 是某一个三角形的两条边 

2\. 存在边 $c$ ，使得 $a,c$ 属于同一个集合且 $b,c$ 属于同一个集合 

  


那么请问，以下连通图的所有边是否都属于同一个集合？ 

## 输入描述:
    
    
    第一行输入 $T$ ,表示 $T$ 组样例
    
    每组样例第一行输入两个正整数 $n,m$
    
    接下来 $m$ 行，第$i$行输入两个正整数 $a_i, b_i$,表示第$i$条边连接 $a_i, b_i$结点
    
      
    
    
    $1\le T\le 10;~2\le n\le 2× 10^5;~1\le m\le 2× 10^5;~n-1\le m;~1\le a_i,b_i\le n$  
    $\sum_{i=1}^{T} n \le 2× 10^5;~ \sum_{i=1}^{T} m \le 2× 10^5$  
    
    
    数据保证图联通，且没有重边和自环

## 输出描述:
    
    
    输出一个字符串表示答案
    
    是输出 "$Yes$"
    
    否输出 "$No$"

示例1 

## 输入
    
    
    1
    3 3
    1 2
    1 3
    3 2

## 输出
    
    
    Yes

示例2 

## 输入
    
    
    1
    4 5
    1 2
    1 4
    2 3
    2 4
    3 4

## 输出
    
    
    Yes

示例3 

## 输入
    
    
    1
    3 2
    1 2
    1 3

## 输出
    
    
    No

示例4 

## 输入
    
    
    1
    4 4
    1 2
    1 4
    2 3
    3 4

## 输出
    
    
    No

## 备注:
    
    
    ![](https://uploadfiles.nowcoder.com/images/20240710/0_1720545117173/0E276EE6DF5C71924EA2BDCE02A2B456)


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

Tags: 图论, 数据结构, 并查集
Difficulty: 2000