牛牛的蜡烛
题号：NC21706
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

牛牛有很多的蜡烛，所有的蜡烛燃烧的速度都是一样的，一根长度为L的蜡烛需要L的时间烧尽
如果在蜡烛的两端同时点燃，则蜡烛的燃烧速度会快一倍

现在牛牛将一些蜡烛摆成了一棵树的形状，一开始，牛牛会同时点燃这棵树的一些叶子（即那些度数为1的点）
火焰烧到某个中间节点时，会同时向邻接的蜡烛烧去，在这个过程中军军不会再去点燃新的蜡烛
整棵树燃烧的总时间为所有的蜡烛都烧尽的时间

牛牛想知道一共有多少种可能燃烧的时间

输入描述:

第一行输入一个整数n,表示树的总结点数
第二行输入n-1个整数ai
第三行输入n-1个整数bi
第四行输入n-1个整数ci
表示ai, bi 之间有一条长度为ci的蜡烛

2 ≤ n ≤ 20

0 ≤ ai ≤ n - 1

0 ≤ bi ≤ n - 1

1 ≤ ci ≤ 1000

输出描述:

输出一个整数
示例1

输入

复制 
3
0 1
1 2
10 1

输出

复制 
2
示例2

输入

复制 
4
0 0 0
1 2 3
1 1 1

输出

复制 
2
示例3

输入

复制 
4
0 0 0
1 2 3
1 2 3

输出

复制 
4
示例4

输入

复制 
9
0 1 1 2 3 3 2 4
1 2 3 4 5 6 7 8
5 3 2 4 6 8 7 1

输出

复制 
7

备注:

子任务1：n <= 5
子任务2：n <= 10
子任务3：无限制