P6655 [YsOI2020] 制高

Ysuperman 特别喜欢玩战略游戏。

游戏地图是一棵 $n$ 个点的有根树，根节点是 $1$ ，除节点 $1$ 外其他节点都有唯一的父亲节点。 每个节点有一个高度，第 $i$ 个节点的高度为 $h_i$ ，我们认为一个节点 $v$ 是“制高点”，当且仅当 $v$ 是根节点或者其父亲节点 $u$ 是“制高点”并且 $h_v\ge h_u$ 。 但是， Ysuperman 并不知道每个节点的父亲具体是哪个，只知道它的父亲编号可能在的区间，其中，节点 $i$ 的父亲可能在的编号范围为 $[l_i,r_i]$ ，保证 $1\le l_i\le r_i

无

无

样例一解释： 共有两种情况，情况一： $2$ 的父亲节点是 $1$ ， $3$ 的父亲节点是 $1$ ，此时 $1,2,3$ 均是“制高点”；情况二： $2$ 的父亲节点是 $1$ ， $3$ 的父亲节点是 $2$ ，由于 $h_2>h_3$ ，所以 $3$ 不是“制高点”，此时 $1,2$ 均是“制高点”。 所以所有情况“制高点”数量的和为 $5$ 。 | $\text{测试点编号}$ | $n$ | $\prod_{i=2}^n(r_i-l_i+1)$ | $\text{特殊性质}$ | | :-----------------: | :------: | :------------------------: | :---------------: | | $1\sim 2$ | $=10$ | $\le 10^6$ | $\text{无}$ | | $3$ | $= 10^5$ | $\le 10^6$ | $\text{无}$ | | $4$ | $= 10^5$ | \\ | $h_i\le h_{i+1}$ | | $5$ | $= 10^5$ | \\ | $h_i>h_{i+1}$ | | $6\sim 12$ | $= 10^3$ | \\ | $\text{无}$ | | $13\sim 20$ | $=10^5$ | \\ | $\text{无}$ | 题目数据保证 $h_i$ 在 `int` 能表示的最大范围内， $1\le l_i\le r_i