Processing math: 3%

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

时间限制:4000MS      内存限制:524288KB

难度:7.0

  • 题目描述

给定一颗 n 个点的树。每个点都一个正整数点权 A_i,你需要支持以下两种操作:

1、询问点 x 和点 y 之间的路径上的所有点(包括点 x 和点 y )的点权是否构成一个从 1 开始的排列。

2、将 A_x 修改为 y

  • 输入格式

第一行一个正整数 T 表示数据组数。

接下来一行输入两个正整数 n,q 表示数的点数和询问个数。

接下来一行 n 个正整数,第 i 个正整数表示 A_i 的初值。

接下来 n-1 行每行两个正整数 u,v 表示树上的一条边 (u,v)

接下来 n 行每行三个正整数 tp,x,y 表示一个操作,其中 tp 表示操作种类。

  • 输出格式

对于每一个操作 1 如果符合条件,输出 Yes ,否则输出 No

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 1 \leq T \leq 101 \leq n,q \leq 2.5 \times 10^51 \leq \sum n,\sum q \leq 5 \times 10^51 \leq u,v,x,y,A_i \leq n1 \leq tp \leq 2

 

 

Source:Codechef LTIME73A QRYLAND


 

 

 

其实是水题。

注意到 1len 的排列是始终不变的,所以可以直接预处理,现在只需要判断两个点权的集合是否相等。

容易想到异或 hash,对于每个 a_i 都随一个权值,记 f_ii 到根路径上权值的异或和,树状数组维护 dfn 即可。

 

 

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注