#P3251. 树上三角形

    ID: 2436 传统题 1000ms 512MiB 尝试: 1364 已通过: 387 难度: 5 上传者: 标签>难度分类普及+/提高-数据结构阈值划分大小情况贪心支配关系枚举与搜索暴力枚举CF1800

树上三角形

树上三角形

题目描述

给定一棵有 nn 个节点的有根树,每个节点有一个点权。操作可以修改一个点的权值,或询问两个节点的简单路径上,能否选择三个不同的节点,使它们的当前点权可以作为一个三角形的三条边长。路径包含两个端点。

输入格式

第一行包含两个整数 n,qn,q,分别为节点数和操作数。第二行包含 nn 个整数,按编号给出每个节点的初始点权。

接下来 n−1n-1 行,每行两个整数 a,ba,b,表示在以 11 为根的树中,aa 是 bb 的父亲。

再接下来 qq 行,每行三个整数 t,a,bt,a,b。

  • t=0t=0 时,询问从节点 aa 到节点 bb 的路径。
  • t=1t=1 时,将节点 aa 的点权修改为 bb。

输出格式

对每次询问输出一行。存在所求的三个节点时输出 Y,否则输出 N。

样例

5 5
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3
N
Y
Y
N

数据规模与约定

n,q≤100000n,q\le100000。点权在 [1,231−1][1,2^{31}-1] 内。

BZOJ 归档题面