P15447 「IXOI R1」Zuyusoft

[NATO](https://www.luogu.com.cn/user/443649) 是柚社子的忠实粉丝。 寒假要来了，他计划在寒假玩完一系列柚社子的游戏。这些游戏构成若干有根树形结构。

**Note: The input and output for this problem are large, please choose appropriate input/output methods.** You are given a forest of rooted trees consisting of $n$ nodes. For node $i(1\le i \le n)$, its parent in the forest is $x_i$ (if $x_i=0$, it means this node is the root of a tree). For each tree, a pair of parameters $(l_a, r_a)$ is given, where $a$ is the root of this tree. Now you need to select several nodes and arrange them into a sequence. A valid sequence is defined as: - For each node $a$ satisfying $x_a=0$, the number of selected nodes in the tree rooted at $a$ must be within $[l_a, r_a]$. - For each selected node, if it is a root or none of its ancestors are selected, then there is no restriction; otherwise, at least one of its ancestors must appear later in the sequence (if this node's position in the sequence is $i$, there exists an ancestor whose position in the sequence is $j$, where $i

The first line contains a positive integer $n$, representing the number of nodes. The next $n$ lines: line $i+1(1\le i\le n)$ contains one to three integers. The first integer $x_i$ represents the parent of node $i$ in the forest. If $x_i=0$, it is followed by two space separated positive integers $[l_i, r_i]$, whose meaning has been given in the problem description.

Output two lines. The first line contains an integer $m$, representing the length of the lexicographically smallest sequence. The second line contains $m$ integers separated by spaces, describing the lexicographically smallest sequence. It can be proved that under the given constraints, at least one valid sequence always exists.

### Example Explanation The smallest lexicographically valid sequence is $2,1,4$ with length $3$, and it can be proved that no lexicographically smaller solution exists. ### Constraints **This problem uses bundled testing.** |Subtask Id|$n\le$ |Special Property|Points | |:---:|:--------:|:--:|:--:| |$0$ |$20$ |No |$10$| |$1$ |$5\times 10^3$|No |$20$| |$2$ |$5\times 10^5$ |A |$10$| |$3$ |$5\times 10^5$ |B |$30$| |$4$ |$5\times 10^5$ |No |$30$| Special property A: It is guaranteed that every tree is a star, i.e., each tree has at most one node with degree greater than $1$, and all nodes $i$ with degree greater than $1$ satisfy $x_i=0$. Special property B: It is guaranteed that $\forall i,l_i=r_i$. For all data, it is guaranteed that: $1\le n\le 5\times 10^5$, $\forall x_i,0\le x_i\le n$. It is guaranteed that for any $[l,r]$ of a tree, $1\le l\le r\le sz$, where $sz$ denotes the number of nodes in the corresponding tree. It is guaranteed that the input graph is a forest.