雾之湖的冰精（三）
题号：NC283612
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

雾之湖里有一只聪慧的冰精，她会进行9以内的加法运算，然而当计算的结果超过9了她的脑子就会陷入红温。

小红拿到了一棵树，每个节点的权值为a_i。她想选择一条简单路径，使得该路径权值和不超过9，请你帮小红计算有多少种选择方案。

我们认为，一个合法的路径应至少包含2个节点。u->v或者v->u我们视为同一条路径。

输入描述:

第一行输入一个正整数n，代表树的节点数量。
第二行输入n个正整数a_i，代表每个节点的权值。
接下来n-1行，每行输入两个正整数u和v，代表树的一条边。
1\leq n \leq 10^5
0\leq a_i \leq 9
1\leq u,v \leq n

输出描述:

输出一个整数，代表合法的路径数量。
示例1

输入

复制 
3
3 4 5
1 2
2 3

输出

复制 
2

说明

存在两条合法的路径：1->2或2->3。请注意，1->3路径权值和为12，超过了9，因此会导致冰精陷入红温。