#P14921. [UJGOI 2023]Graph? Are you sure?

    ID: 14137 传统题 1500ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200并查集数据结构数学字符串哈希图论最短路

[UJGOI 2023]Graph? Are you sure?

题目描述

初始有 nn 个顶点,没有边。每条被加入的边上都写着一个整数 cic_i。

对于同一个连通块内的两个顶点 aa 和 bb,定义它们之间的简单路径为从 aa 到 bb 的最短路径。若一条简单路径上,每一种数值的出现次数都是偶数,则称这条路径是 好的。

你需要回答 qq 次询问,询问共有 44 种类型:

  • 1 u v c1\ u\ v\ c(1≤c≤4⋅1091 \le c \le 4 \cdot 10^9):加入一条连接顶点 uu 和 vv、边权为 cc 的边;
  • 2 u v2\ u\ v:判断顶点 uu 和 vv 之间的简单路径是否是好的。如果它们之间不存在路径,输出 −1-1;
  • 3 u3\ u:输出满足下列条件的点对 (a,b)(a,b) 的数量:1≤a<b≤n1 \le a < b \le n,aa 和 bb 与 uu 属于同一个连通块,并且 aa 到 bb 的路径是好的;
  • 44:输出满足下列条件的点对 (a,b)(a,b) 的数量:1≤a<b≤n1 \le a < b \le n,aa 到 bb 的路径是好的,并且 aa 到 bb 存在路径。

保证所有类型 11 的询问中,加入的边都会连接两个不同的连通块。

输入格式

第一行包含两个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)和 qq(1≤q≤2⋅1051 \le q \le 2 \cdot 10^5),分别表示顶点数和询问数。

接下来 qq 行,每行包含一条询问的描述。每条询问的第一个整数 tit_i 表示询问类型。

  • 若 ti=1t_i=1,后面跟着 33 个整数 u,v,cu,v,c(1≤u≠v≤n1 \le u \ne v \le n,1≤c≤4⋅1091 \le c \le 4 \cdot 10^9);
  • 若 ti=2t_i=2,后面跟着 22 个整数 u,vu,v(1≤u,v≤n1 \le u,v \le n);
  • 若 ti=3t_i=3,后面跟着 11 个整数 uu(1≤u≤n1 \le u \le n);
  • 若 ti=4t_i=4,后面不再跟随其他整数。

输出格式

对于每个类型 22 的询问,输出:

  • -1:如果当前不存在对应的简单路径;
  • YES:如果这条简单路径是 好的;
  • NO:否则。

对于每个类型 33 或类型 44 的询问,输出一个整数,表示对应询问的答案。

你需要按照输入中询问出现的顺序依次回答。

输入 #1

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

输出 #1

-1
1
NO
2
YES
NO
2

子任务

  1. (55 分)对所有 ti=1t_i=1 的询问,均有 ui=1u_i=1;
  2. (55 分)n,q≤20n,q \le 20;
  3. (77 分)n,q≤1000n,q \le 1000;
  4. (33 分)ti≤ti+1t_i \le t_{i+1},ti≤2t_i \le 2,c=1c=1;
  5. (66 分)ti≤ti+1t_i \le t_{i+1},ti≤2t_i \le 2,c≤8c \le 8;
  6. (1111 分)ti≤ti+1t_i \le t_{i+1},ti≤2t_i \le 2;
  7. (99 分)q=nq=n,对 1≤i<n1 \le i < n 有 ti=1t_i=1,且 tq=4t_q=4;
  8. (1717 分)存在一个整数 ee,使得对所有 1≤i≤e1 \le i \le e 都有 ti=1t_i=1,并且对所有 e<j≤qe<j\le q 都有 tj≠1t_j\ne 1;
  9. (99 分)c≤1000c \le 1000,图和测试数据随机生成。具体而言,对每个顶点 vv(2≤v≤n2 \le v \le n)随机选择 pvp_v(1≤pv<v1 \le p_v < v),然后生成一个随机排列 permperm,并令 v=permvv=perm_v,pv=permpvp_v=perm_{p_v}。询问类型随机选择(如果没有边可加,则不会选择第一类询问),询问中的所有值也随机选取;
  10. (2828 分)无额外限制。