HackerRank Number Theory – Matrix Tree

Challenge: Matrix Tree

Subdomeniu: Number Theory (number-theory)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736439

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/matrix-tree/problem

Cerinta

[Sevenkplus](http://sevenkplus.com/) has a rooted tree with $N$ vertices. The vertices are labeled from $1$ to $N$. $1$ is the root of the tree. Each vertex $v$ has a weight $W_v$.  
He forms a $N \times N$ matrix $M$ from the tree. $M$ is defined by  
$$M(x,y)=W_{lca(x,y)}$$  
where $lca(x,y)$ is the lowest common ancestor of vertex $x$ and vertex $y$.  
He wants to calculate the determinant of $M$.  

**Input Format**  
First line contains the number of vertices, $N$.  
Second line contains $N$ numbers, $W_1 ~ W_2 ~ \cdots ~ W_N$ separated by a space.   
This is followed by $N-1$ lines. Each line contains two numbers $x$, $y$, denoting that there is an edge between $x$  and $y$.  

**Output Format**  
Output one line, the determinant of $M$ modulo $(10^9 + 7)$.

**Constraints**  
$1 \le N \le 10^5$   
$\forall i, 0 \le W_i \le 10^9$. 

**Sample Input**

	3
	1 2 3
	1 2
    1 3

**Sample Output**

	2

**Explanation**

$$
M =  \left[ {\begin{array}{ccc}
   1 & 1 & 1\\\
   1 & 2 & 1\\\
   1 & 1 & 3
  \end{array} } \right ]
$$

Then, $$|M| = 1\times \left[ {\begin{array}{cc}
   2 & 1\\\
   1 & 3
  \end{array} } \right ] - 1 \times \left[ {\begin{array}{cc}
   1 & 1\\\
   1 & 3
  \end{array} } \right ] + 1 \times \left[ {\begin{array}{cc}
   1 & 2\\\
   1 & 1
  \end{array} } \right ]$$. 

Hence $|M| = (1 \times 5) - (1\times 2) + (1 \times -1) = 2$

**Timelimits**  
Timelimits for this challenge is given [here](https://www.hackerrank.com/environment)

Cod sursa

//matrix-tree.cpp
//Matrix Tree
//Ad Infinitum - Math Programming Contest August'14
//Author: derekhh

#include<iostream>
#include<vector>
using namespace std;

int w[100001];
vector<int> v[100001];
bool visited[100001];
long long ans;

const int MOD = 1000000007;

void dfs(int root, int p)
{
	visited[root] = true;
	int sz = (int)v[root].size();
	for (int i = 0; i < sz; i++)
		if (!visited[v[root][i]])
			dfs(v[root][i], root);
	ans = (ans * (w[root] - w[p] + MOD)) % MOD;
}

int main()
{
	ans = 1;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> w[i];
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	cout << ans << endl;
	return 0;
}