The Grass Type
Tag(s):

## Data Structures, Disjoint set, Graph, Map, Medium-Hard, Tree

Problem
Editorial
Analytics

Ash Catch'Em apparently loves only two things in his life: graph theory, and his grass type Poke'mons. And instead of using his grass type Poke'mons to be a better trainer, he just arranges them in a graph, and solve random questions.

Currently Ash is playing with his Bulbasaur. With its help, he has managed to create a tree of N vertices which are rooted at 1. Each of the vertices have labels namely A1, A2, ... , AN -1, AN.

Ash is trying to explain the concept of LCA, known as the Lowest Common Ancestor to his Poke'mons, so that they'll be able to understand how and what kind of evolution will they have to go through in future.

But we all know know that Ash is a little... slow at explaining things. So, he wants you to find the total number of unordered pairs (u,v) such that ALCA(u,v) == Au * Av, where u != v . He thinks that this equation will help him figure out the logic behind the evolution of grass type Poke'mons. Can you help him find the total number of such pairs?

Input format:
The first line consists of a single integer N denoting the total number of vertices in the tree created by Bulbasaur using Leech Seed. The next N-1 lines consist of two integers u and v denoting an edge. The next line will consist of N integers A1, A2, ... , AN -1, AN.

Output format:
Output the total number of pairs (u,v) such that ALCA(u,v) == Au * Av and u!=v.

Constraints:
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109

Reference:

SAMPLE INPUT
7
1 2
1 3
2 4
2 5
5 6
5 7
6 8 3 2 8 2 4
SAMPLE OUTPUT
4
Explanation

Here all the possible pairs are (3,4), (3,6), (4,7), (6,7)

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Data Structures > Hash Tables
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Math > Number Theory