Soluție HackerRank pentru Matrix Tree, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Matrix Tree
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
[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 × 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 ~ ·s ~ 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 ≤ N ≤ 10^5
forall i, 0 ≤ W_i ≤ 10^9.
Sample Input
3
1 2 3
1 2
1 3
Sample Output
2
Explanation
M = ≤ft[ {begin{array}{ccc}
1 & 1 & 1
1 & 2 & 1
1 & 1 & 3
end{array} } right ]
Then, |M| = 1× ≤ft[ {begin{array}{cc}
2 & 1
1 & 3
end{array} } right ] - 1 × ≤ft[ {begin{array}{cc}
1 & 1
1 & 3
end{array} } right ] + 1 × ≤ft[ {begin{array}{cc}
1 & 2
1 & 1
end{array} } right ].
Hence |M| = (1 × 5) - (1× 2) + (1 × -1) = 2
Timelimits
Timelimits for this challenge is given [here](https://www.hackerrank.com/environment)
Cod sursă
//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;
}