「十二省联考 2019」字符串问题【后缀数组 + 线段树】

Time Limit: 6 Sec Memory Limit: 1024 MB

Description

给定一个字符串 SS,定义 S\lvert S \rvert 表示 SS 的长度,子串 S(L,R)S(L, R) 为由 SS 中从左往右数第 LL 个字符到第 RR 个字符连接形成的字符串。两个字符串 S,TS, T 相加 S+TS + T 表示在 SS 后紧挨着写下 TT 得到的长度为 S+T\lvert S \rvert + \lvert T \rvert 的字符串。

Tiffany\text{Tiffany} 将从中划分出 nan_a 个子串作为 A\text{A} 类串,第 ii 个为 Ai=S(lai,rai)A_i = S(la_i, ra_i)

类似地,Yazid\text{Yazid} 将划分出 nbn_b 个子串作为 B\text{B} 类串,第 ii 个为 bi=S(lbi,rbi)b_i = S(lb_i, rb_i)

给定 mmAB\text{AB} 类串之间的单向边。规定 A\text{A} 类串 AiA_iAjA_j 之间有单向边当且仅当存在一个 B\text{B} 类串,其为 AjA_j 的前缀,且与 AiA_i 有边相连。

求最长链的长度。如果长度为无限长,输出 1-1

Input

输入的第一行包含一个整数 TT 表示数据组数。接下来依次描述每组数据,对于每组数据:

  • 11 行一个只包含小写字母的字符串 SS
  • 22 行一个整数 nan_a,表示 A\text{A} 类串的数目。接下来 nan_a 行,每行 22 个用空格隔开的整数。
    • ii 行的两个数分别为 lai,raila_i, ra_i,描述第 iiA\text{A} 类串。
  • 接下来一行一个整数 nbn_b,表示 B\text{B} 类串的数目。接下来 nbn_b 行,每行 22 个用空格隔开的整数。
    • ii 行的两个数分别为 lbi,rbilb_i, rb_i,描述第 ii 个 B 类串。
  • 接下来一行一个整数 mm,表示边数。接下来 mm 行,每行 22 个用空格隔开的整数。
    • 每行的两个整数 x,yx, y,表示第 xxA\text{A} 类串和第 yyB\text{B} 类串之间有单向边。
    • 保证 1xna,1 \leqslant x \leqslant n_a, 1ynb1 \leqslant y \leqslant n_b。保证没有重边。

Output

依次输出每组数据的答案,对于每组数据:

  • 一行一个整数表示最长链的长度。如果可以是无限长,输出 −1。

查看更多

「NOIP 2018」保卫王国【DP + LCT】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

给定一棵 nn 个点的树,选第 ii 个点的费用是 pip_i。有 mm 个询问,每次钦定两个点选或不选,求出整棵树的最小覆盖的费用,无法覆盖输出 1-1

Input

第一行包含两个整数 n,mn, m 和一个字符串 type\text{type},表示点数、询问数和数据类型。

第二行包含 nn 个整数 pip_i,表示选第 ii 个点的费用。

接下来 n1n - 1 行,每行包含两个整数 u,vu, v,表示树的边 (u,v)(u, v)

接下来 mm 行,每行包含四个整数 a,b,x,ya, b, x, yxx 表示钦定点 aa// 不选,yy 表示钦定点 bb// 不选。

Output

输出 TT 行,每行包含一个整数,表示对应询问的最小费用,无解输出 1-1

查看更多

「UOJ 207」共价大爷游长沙【LCT】

Time Limit: 2 Sec Memory Limit: 512 MB

Description

有一个 nn 个结点的树,和一个包含一些点对 (x,y)(x, y) 的可重集合 SS,有四种操作:

  • 1 x y u v1\ x\ y\ u\ v:删除连接 (x,y)(x, y) 的边,加上连接 (u,v)(u, v) 的边,保证操作完仍然是树。
  • 2 x y2\ x\ y:在 SS 中加入点对 (x,y)(x, y)
  • 3 x3\ x:删除第 xx 个加入 SS 中的点对。
  • 4 x y4\ x\ y:询问连接 (x,y)(x, y) 的边是否被所有 SS 中点对之间的路径经过,保证 SS 非空。

Input

第一行包含一个整数 id\text{id},表示测试数据编号。

第二行包含两个整数 n,mn, m,表示点数和操作数。

接下来 n1n - 1 行,每行包含两个整数 x,yx, y,表示树的边 (x,y)(x, y)

接下来 mm 行,每行描述一个操作,格式见题目描述。

Output

输出 TT 行,每行包含一个整数,表示对应数据中食堂完成所有菜所需的最少时间。

查看更多