#P18669. Puzzle: Kusabi

    ID: 18005 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-树形 DP排序贪心支配关系同向双指针不变量分析

Puzzle: Kusabi

Puzzle: Kusabi

“随机猜测每个符号所对应的含义,成功的概率只有 16.7%。”——Freddie Hand

Grammy 是一位解谜高手。今天,她正在玩一种 Kusabi 谜题的变体。

给定一棵以顶点 11 为根的树,树上部分顶点写有汉字标记。根顶点 11 没有标记。有标记的顶点可以写着“长”(输入记作 Chang)、“短”(Duan)或“同”(Tong)。你需要把所有有标记的顶点两两配对,并标记每对顶点之间最短路径上的所有边,满足:

  • 每个有标记的顶点必须与另一个有标记的顶点恰好配对一次。
  • 写着“长”的顶点到根的距离,必须严格大于其配对顶点到根的距离。
  • 写着“短”的顶点到根的距离,必须严格小于其配对顶点到根的距离。
  • 写着“同”的顶点到根的距离,必须等于其配对顶点到根的距离。
  • 树上的每条边至多被标记一次。

这里距离是树上路径的边数。限制针对边,路径可以经过同一个顶点。每对的两个端点都必须满足各自标记的要求。

下面第一张是只有线索的原题图,第二张是一个可行解。红色边表示被某对顶点的路径标记的边。

原题线索图

原题可行解图

Grammy 当然知道如何解开这个谜题,不过她决定考考你。请你求出一个解,或者判断无解。

输入格式

第一行包含一个整数 nn,1≤n≤1051\le n\le10^5,表示顶点数。

接下来 n−1n-1 行,每行包含两个整数 i,pii,p_i 和一个字符串 tit_i,表示顶点 ii 与 pip_i 之间有一条边,且顶点 ii 的标记类型为 tit_i。其中

$$1\le p_i<i\le n,\qquad t_i\in\{\texttt{Chang},\texttt{Duan},\texttt{Tong},\texttt{-}\}.$$

- 表示该顶点没有标记。保证这些行按 i=2,3,…,ni=2,3,\ldots,n 的顺序给出。保证至少有一个有标记的顶点;根顶点 11 没有标记。

输出格式

如果不存在解,输出一行 NO。

否则第一行输出 YES,随后每行输出两个整数 ui,viu_i,v_i,表示一对配对顶点。输出必须使所有有标记的顶点恰好出现一次,并满足所有条件。如果存在多个解,输出任意一个。

样例输入 1

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

样例输出 1

YES
6 8
5 4

样例输入 2

10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang

样例输出 2

YES
9 8
3 10
2 6
7 5