[JSOI2010] 游戏

题目描述

JSOI 集训队的小 L,小 H,小 X 在紧张的训练之余,总是喜欢玩一个称之为“取数”的游戏来调节自己: 这是一个人玩的游戏,仅仅需要一张白纸和一支笔。玩家在纸上随机写下一行共 $n$ 个整数,形成一个数列,就可以开始游戏了。 每次玩家从原数列最左端或最右端选择一个数,将它从原数列中划去,并写在下一行。当原数列的数全部被划去后,在第二行就出现了一个新的长度为 $n$ 的数列,记为 $S$。将按照如下方式计算数列 $S$ 的分数 $P$: $$P=S_1\times 5^0+S_2\times 5^1+\cdots+S_n\times 5^{n-1}$$ 算出分数 $P$ 后,将其转为二进制表示,如果末三位数字是 $011$ 的话,玩家就取得了游戏的胜利,否则就失败了。 在玩了很多次这个游戏后,小 L,小 H,小 X 发现一个重要的事实:对于某些随机写下的数列,是无论如何也无法取得游戏胜利的,这样的数列被称为“刁列”,其它的数列则被 称为“良列”。 这个游戏虽然趣味性极强,但有一个弊端:每次游戏前需要花很多时间来写出这个随机数列,这一点一直深深困扰着小 L,小 H 和小 X。 直到在今年省选前的那天晚上,小 L 想出了一个惊为天人的创意,一举攻克了这个难题:他们先在纸上画出一颗庞大的无根树(共 $m$ 个结点),每个结点上写下一个整数。当想要玩游戏时,玩家只需随便选择两个结点,通过找出连接这两个结点的那条唯一的路径,将路径上所有结点(包括两个端点)上标注的整数按路径的顺序列出来,就得到了一个数列,然后就可以在这个数列上玩游戏了。如果选择的两个端点分别是树上结点 $v_i$ 和结点 $v_j$,得到的数列就简记为 $i\sim j$。当然,如前所述,$i\sim j$ 这个数列也有“良列”和“刁列”两种可能。 他们发现这样改进以后真的方便了很多!不仅如此,还给游戏带来了一些新的趣味。比如小 X 就声称他发现了一个重要的规律:数列的属性是具有传递性的,即:对于任意互不相同的 $i,j,k$ 有: - 如果 $i\sim j$ 是良列,$j\sim k$ 是良列,则 $i\sim k$ 是良列。 - 如果 $i\sim j$ 是刁列或 $j\sim k$ 是刁列,则 $i\sim k$ 是刁列。 这个结论出奇地优美,但很快就被小 H 找到了反例,这让小 X 心情沮丧。小 L 为了安慰小 X,说:不如我们来看看你这个结论在多少情况下是成立的吧。 小 X 振作了起来,大家一起投入了繁重的工作中。他们要找出存在多少个三元组 $(i,j,k)$,其中 $i<j<k$,使得 $i,j,k$ 满足小 X 发现的传递性结论。

输入输出格式

输入格式


第一行一个整数 $m$,代表无根树的节点个数。 接下来 $m$ 行,每行两个整数 $f_i,x_i$,其中 $f_i<i$。$f_i$ 表示节点 $v_i$ 的父节点编号,如果 $f_i=0$ 则该节点为根,$x_i$ 表示节点 $v_i$ 上写的数。

输出格式


一行一个整数,表示答案。

输入输出样例

输入样例 #1

3
0 3
1 5
1 7

输出样例 #1

0

输入样例 #2

5
0 8626
1 29255
2 21486
2 26193
1 22439

输出样例 #2

7

说明

### 数据范围 对于 $10\%$ 的数据,$1\leq m\leq 5$。 对于 $30\%$ 的数据,$1\leq m\leq 100$。 对于 $50\%$ 的数据,$1\leq m\leq 10^3$。 对于 $100\%$ 的数据,$1\leq m\leq 10^5$。