Dado un árbol con N vértices y N-1 Aristas. Definamos una función F(a, b) que sea igual al peso mínimo del borde en la ruta entre los Nodes a y b. La tarea es calcular el producto de todos estos F(a, b). Aquí a&b son pares desordenados y a!=b.
Entonces, básicamente, necesitamos encontrar el valor de:
where 0<=i<j<=n-1.
En la entrada, se nos dará el valor de N y luego seguirán N-1 líneas. Cada línea contiene 3 enteros u, v, w que denotan el borde entre el Node u y v y su peso w. Dado que el producto será muy grande, imprímalo en módulo 10^9+7.
Ejemplos:
Input :
N = 4
1 2 1
1 3 3
4 3 2
Output : 12
Given tree is:
1
(1)/ \(3)
2 3
\(2)
4
We will calculate the minimum edge weight between all the pairs:
F(1, 2) = 1 F(2, 3) = 1
F(1, 3) = 3 F(2, 4) = 1
F(1, 4) = 2 F(3, 4) = 2
Product of all F(i, j) = 1*3*2*1*1*2 = 12 mod (10^9 +7) =12
Input :
N = 5
1 2 1
1 3 3
4 3 2
1 5 4
Output :
288
Si observamos detenidamente, veremos que si hay un conjunto de Nodes en los que el peso mínimo de la arista es w y si agregamos un Node a este conjunto que conecta el Node con todo el conjunto por una arista de peso W tal que W< w Entonces, la ruta formada entre el Node agregado recientemente y todos los Nodes presentes en el conjunto tendrán un peso mínimo W.
Entonces, aquí podemos aplicar el concepto de Unión de conjunto disjunto para resolver el problema.
Primero, ordene la estructura de datos de acuerdo con el peso decreciente. Asigne inicialmente todos los Nodes como un solo conjunto. Ahora, cuando combinemos dos conjuntos, haga lo siguiente:
Product=(present weight)^(size of set1*size of set2).
Multiplicaremos el valor de este producto por todos los bordes del árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
// Function to return (x^y) mod p
int power(int x, unsigned int y, int p)
{
int res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Declaring size array globally
int size[300005];
int freq[300004];
vector<pair<int, pair<int, int> > > edges;
// Initializing DSU data structure
void initialize(int Arr[], int N)
{
for (int i = 0; i < N; i++) {
Arr[i] = i;
size[i] = 1;
}
}
// Function to find the root of ith
// node in the disjoint set
int root(int Arr[], int i)
{
while (Arr[i] != i) {
i = Arr[i];
}
return i;
}
// Weighted union using Path Compression
void weighted_union(int Arr[],
int size[], int A, int B)
{
int root_A = root(Arr, A);
int root_B = root(Arr, B);
// size of set A is small than size of set B
if (size[root_A] < size[root_B]) {
Arr[root_A] = Arr[root_B];
size[root_B] += size[root_A];
}
// size of set B is small than size of set A
else {
Arr[root_B] = Arr[root_A];
size[root_A] += size[root_B];
}
}
// Function to add an edge in the tree
void AddEdge(int a, int b, int w)
{
edges.push_back({ w, { a, b } });
}
// Build the tree
void MakeTree()
{
AddEdge(1, 2, 1);
AddEdge(1, 3, 3);
AddEdge(3, 4, 2);
}
// Function to return the required product
int MinProduct()
{
int result = 1;
// Sorting the edges with respect to its weight
sort(edges.begin(), edges.end());
// Start iterating in decreasing order of weight
for (int i = edges.size() - 1; i >= 0; i--) {
// Determine Current edge values
int curr_weight = edges[i].first;
int Node1 = edges[i].second.first;
int Node2 = edges[i].second.second;
// Calculate root of each node
// and size of each set
int Root1 = root(freq, Node1);
int Set1_size = size[Root1];
int Root2 = root(freq, Node2);
int Set2_size = size[Root2];
// Using the formula
int prod = Set1_size * Set2_size;
int Product = power(curr_weight, prod, mod);
// Calculating final result
result = ((result % mod) *
(Product % mod)) % mod;
// Weighted union using Path Compression
weighted_union(freq, size, Node1, Node2);
}
return result % mod;
}
// Driver code
int main()
{
int n = 4;
initialize(freq, n);
MakeTree();
cout << MinProduct();
}
Java
// Java Implementation of above approach
import java.util.ArrayList;
import java.util.Collections;
public class Product {
// to store first vertex, second vertex and weight of
// the edge
static class Edge implements Comparable<Edge> {
int first, second, weight;
Edge(int x, int y, int w)
{
this.first = x;
this.second = y;
this.weight = w;
}
@Override public int compareTo(Edge edge)
{
return this.weight - edge.weight;
}
}
static int mod = 1000000007;
// Function to return (x^y) mod p
static int power(int x, int y, int p)
{
int res = 1;
x = x % p;
while (y > 0) {
if ((y & 1) == 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Declaring size array globally
static int size[] = new int[300005];
static int freq[] = new int[300004];
static ArrayList<Edge> edges = new ArrayList<Edge>();
// Initializing DSU data structure
static void initialize(int Arr[], int N)
{
for (int i = 0; i < N; i++) {
Arr[i] = i;
size[i] = 1;
}
}
// Function to find the root of ith
// node in the disjoint set
static int root(int Arr[], int i)
{
while (Arr[i] != i) {
i = Arr[i];
}
return i;
}
// Weighted union using Path Compression
static void weighted_union(int Arr[], int size[], int A,
int B)
{
int root_A = root(Arr, A);
int root_B = root(Arr, B);
// size of set A is small than size of set B
if (size[root_A] < size[root_B]) {
Arr[root_A] = Arr[root_B];
size[root_B] += size[root_A];
}
// size of set B is small than size of set A
else {
Arr[root_B] = Arr[root_A];
size[root_A] += size[root_B];
}
}
// Function to add an edge in the tree
static void AddEdge(int a, int b, int w)
{
edges.add(new Edge(a, b, w));
}
// Build the tree
static void MakeTree()
{
AddEdge(1, 2, 1);
AddEdge(1, 3, 3);
AddEdge(3, 4, 2);
}
// Function to return the required product
static int MinProduct()
{
int result = 1;
// Sorting the edges with respect to its weight
// ascending order
Collections.sort(edges);
// Start iterating in decreasing order of weight
for (int i = edges.size() - 1; i >= 0; i--) {
// Determine Current edge values
int curr_weight = edges.get(i).weight;
int Node1 = edges.get(i).first;
int Node2 = edges.get(i).second;
// Calculate root of each node
// and size of each set
int Root1 = root(freq, Node1);
int Set1_size = size[Root1];
int Root2 = root(freq, Node2);
int Set2_size = size[Root2];
// Using the formula
int prod = Set1_size * Set2_size;
int Product = power(curr_weight, prod, mod);
// Calculating final result
result
= ((result % mod) * (Product % mod)) % mod;
// Weighted union using Path Compression
weighted_union(freq, size, Node1, Node2);
}
return result % mod;
}
// Driver code
public static void main(String[] args)
{
int n = 4;
initialize(freq, n);
MakeTree();
System.out.println(MinProduct());
}
}
// This code is contributed by jainlovely450
Python3
# Python3 implementation of the approach mod = 1000000007 # Function to return (x^y) mod p def power(x: int, y: int, p: int) -> int: res = 1 x %= p while y > 0: if y & 1: res = (res * x) % p y = y // 2 x = (x * x) % p return res # Declaring size array globally size = [0] * 300005 freq = [0] * 300004 edges = [] # Initializing DSU data structure def initialize(arr: list, N: int): for i in range(N): arr[i] = i size[i] = 1 # Function to find the root of ith # node in the disjoint set def root(arr: list, i: int) -> int: while arr[i] != i: i = arr[i] return i # Weighted union using Path Compression def weighted_union(arr: list, size: list, A: int, B: int): root_A = root(arr, A) root_B = root(arr, B) # size of set A is small than size of set B if size[root_A] < size[root_B]: arr[root_A] = arr[root_B] size[root_B] += size[root_A] # size of set B is small than size of set A else: arr[root_B] = arr[root_A] size[root_A] += size[root_B] # Function to add an edge in the tree def AddEdge(a: int, b: int, w: int): edges.append((w, (a, b))) # Build the tree def makeTree(): AddEdge(1, 2, 1) AddEdge(1, 3, 3) AddEdge(3, 4, 2) # Function to return the required product def minProduct() -> int: result = 1 # Sorting the edges with respect to its weight edges.sort(key = lambda a: a[0]) # Start iterating in decreasing order of weight for i in range(len(edges) - 1, -1, -1): # Determine Current edge values curr_weight = edges[i][0] node1 = edges[i][1][0] node2 = edges[i][1][1] # Calculate root of each node # and size of each set root1 = root(freq, node1) set1_size = size[root1] root2 = root(freq, node2) set2_size = size[root2] # Using the formula prod = set1_size * set2_size product = power(curr_weight, prod, mod) # Calculating final result result = ((result % mod) * (product % mod)) % mod # Weighted union using Path Compression weighted_union(freq, size, node1, node2) return result % mod # Driver Code if __name__ == "__main__": # Number of nodes and edges n = 4 initialize(freq, n) makeTree() print(minProduct()) # This code is contributed by # sanjeev2552
Javascript
<script>
// JavaScript implementation of the approach
const mod = 1000000007
// Function to return (x^y) mod p
function power(x, y, p){
let res = 1
x %= p
while(y > 0){
if(y & 1)
res = (res * x) % p
y = Math.floor(y / 2)
x = (x * x) % p
}
return res
}
// Declaring size array globally
let size = new Array(300005).fill(0)
let freq = new Array(300004).fill(0)
let edges = []
// Initializing DSU data structure
function initialize(arr, N){
for(let i=0;i<N;i++){
arr[i] = i
size[i] = 1
}
}
// Function to find the root of ith
// node in the disjoint set
function root(arr, i){
while(arr[i] != i)
i = arr[i]
return i
}
// Weighted union using Path Compression
function weighted_union(arr, size, A, B){
let root_A = root(arr, A)
let root_B = root(arr, B)
// size of set A is small than size of set B
if(size[root_A] < size[root_B]){
arr[root_A] = arr[root_B]
size[root_B] += size[root_A]
}
// size of set B is small than size of set A
else{
arr[root_B] = arr[root_A]
size[root_A] += size[root_B]
}
}
// Function to add an edge in the tree
function AddEdge(a, b, w){
edges.push([w, [a, b]])
}
// Build the tree
function makeTree(){
AddEdge(1, 2, 1)
AddEdge(1, 3, 3)
AddEdge(3, 4, 2)
}
// Function to return the required product
function minProduct(){
let result = 1
// Sorting the edges with respect to its weight
edges.sort((a,b)=>a[0]-b[0])
// Start iterating in decreasing order of weight
for(let i=edges.length - 1;i>=0;i--){
// Determine Current edge values
let curr_weight = edges[i][0]
let node1 = edges[i][1][0]
let node2 = edges[i][1][1]
// Calculate root of each node
// and size of each set
let root1 = root(freq, node1)
let set1_size = size[root1]
let root2 = root(freq, node2)
let set2_size = size[root2]
// Using the formula
let prod = set1_size * set2_size
let product = power(curr_weight, prod, mod)
// Calculating final result
result = ((result % mod) * (product % mod)) % mod
// Weighted union using Path Compression
weighted_union(freq, size, node1, node2)
}
return result % mod
}
// Driver Code
// Number of nodes and edges
let n = 4
initialize(freq, n)
makeTree()
document.write(minProduct(),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
12
Complejidad del tiempo: O(N*logN)
Publicación traducida automáticamente
Artículo escrito por rajankur100 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA