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 10\),\(1 \leq n,q \leq 2.5 \times 10^5\),\(1 \leq \sum n,\sum q \leq 5 \times 10^5\),\(1 \leq u,v,x,y,A_i \leq n\),\(1 \leq tp \leq 2\)。

 

 

Source:Codechef LTIME73A QRYLAND


 

 

 

其实是水题。

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

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

 

 

 

发表回复

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