流年烹茶

5
3 1 3
3 2 3
4 2 3
5 3 2
5 3 5

6
3 0
24 24
0 60 0
60 80 0

Hint
对于第一组数据：
显然题目的限制相当于计数 3 阶排列个数，则 3! = 6。

对于第二组数据：
若只有一棵树，显然其必然是如下形态：

  ○
 / \
○   ○


故只需要选择根的标号，方案数为 3。
若有两棵树，显然不存在满足条件的方案。

对于第三组数据：
若只有一棵树，显然其必然是如下形态：

    ○
   / \
  ○   ○
 /
○

故方案数是 C(4, 1) * C(3, 2) * 2 = 24。
若有两棵树，显然其必然是如下形态之一：

    ○            ○
   / \
  ○   ○   ,  
          or
    ○            ○
    |            |
    ○     ,      ○

故方案数为 C(4, 3) * 3 + C(4, 2) * 2 * 2 / 2 = 24。

对于第四组数据：  
若只有一棵树，由于 s=3 > k=2 故必然满足不了，方案数为 0。
若有两棵树，显然其必然是如下形态：

    ○            ○
   / \           |
  ○   ○   ,      ○

故方案数为 C(5, 3) * 3 * 2 = 60。
若有三棵树，考虑根的个数 3 加上 s=3 为 6>n=5，故必然满足不了。

对于第五组数据：
我有一个绝妙的解释，但这里空间太小写不下。