All Tracks Algorithms Graphs Depth First Search Problem

The Grass Type
Tag(s):

Data Structures, Disjoint Set, Map, Medium-Hard, Trees

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 A$$1$$, A$$2$$, ... , A$$N$$ -$$1$$, A$$N$$.

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 A$$1$$, A$$2$$, ... , A$$N$$ -$$1$$, A$$N$$.

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 ≤ $$A$$i ≤ 109

Reference:
enter image description here

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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications