13442: 笛卡尔树
Memory Limit:128 MB
Time Limit:3.000 S
Judge Style:Text Compare
Creator:
Submit:2
Solved:0
Description
【问题描述】
笛卡尔树(Cartesian Tree)是一种特殊的二叉搜索树。让我们复习一下:二叉搜索树是一颗有根二叉树,并且对于每个结点x都满足:它左子树中的任何结点的权值都小于x的权值,它右子树中任何结点的权值都大于x的权值。让我们形式化定义:假设x的左子树为L(x),x的右子树为R(x),x的权值为k(x)。则一颗满足如下条件的二叉树称为二叉搜索树:
如果点y在L(x)中,则k(y)<k(x);如果点z在R(x)中,则k(z)>k(x)。
一颗二叉搜索树称为笛卡尔树,当且仅当我们给每个点都附加一个权值a(x),且每个点的a权值都严格小于它左右子树中的点的a权值。也就是说:如果点y是x的父亲,则a(y)<a(x)。
因此,一颗笛卡尔树就是一颗二叉树,对于每个结点有两个权值(k,a),且满足上面三条性质。
给定一个点,请你构造出一颗笛卡尔树。
Input
第一行是一个整数n(1=<n<=50000),表示给定结点的个数。
接下来n行,每行两个整数k(i),a(i),表示点i的两个权值。题目保证同类权值不出现重复,也就是说对于任意i<>j,一定有k(i)<>k(j),且a(i)<>a(j)。权值都是不超过50000的正整数。
Output
第一行输出解的情况。如果可以构造出一颗笛卡尔树,输出"yes",否则输出"no"。
如果可以构造,那么接下来输出n行,每行3个整数,分别表示第i个结点的父亲、左儿子、右儿子的编号。顶点编号都是从1到n的,0表示空。顶点的输出顺序与输入顺序一致。
Sample Input Copy
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
Sample Output Copy
yes
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0