Подсчет всех возможных путей в дереве так, чтобы узел X не появлялся перед узлом Y

Опубликовано: 8 Января, 2022

Для Дерева, состоящего из N узлов, имеющих значения в диапазоне [0, N - 1] и (N - 1) ребер, и двух узлов X и Y , задача состоит в том, чтобы найти количество возможных путей в Дереве, таких, что узел X не появляется перед узлом Y в пути.

Примеры:

Input: N = 5, A = 2, B = 0, Edges[][] = { {0, 1}, {1, 2}, {1, 3}, {0, 4} } 
Output: 18 
Explanation: 
Since (X, Y) and (Y, X) are being considered different, so the count of all possible paths connecting any two pair of vertices = 2 * 5C2 = 20. 
Out of these 20 pairs, those paths cannot be chosen which consist of both nodes 2 and 0 as well as Node 2 appearing before Node 0. 
There are two such paths (colored as green) which are shown below: 
 

 

So there are total 20 – 2 = 18 such paths.
Input: N = 9, X = 5, Y = 3, Edges[][] = { {0, 2}, {1, 2}, {2, 3}, {3, 4}, {4, 6}, {4, 5}, {5, 7}, {5, 8} } 
Output: 60 
Explanation: 
Since (X, Y) and (Y, X) are being considered different, so the count of all possible paths connecting any two pair of vertices = N * (N – 1) = 9 * 8 = 72. 
On observing the diagram below, any path starting from a Node in the subtree of Node 5, denoted by black, connecting to the vertices passing through the Node 3, denoted by green, will always have 5 appearing before 3 in the path. 
 

Therefore, total number of possible paths = (Total Nodes grouped in black) * (Total Nodes grouped in green) = 3 * 4 = 12. 
Therefore, the final answer = 72 – 12 = 60 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:
Идея состоит в том, чтобы найти комбинацию пар узлов, при которой узел X всегда будет появляться перед узлом Y на пути, соединяющем их. Затем вычтите количество таких пар из общего количества возможных пар узлов = N C 2 . Считайте узел Y корневым. Теперь любой путь, который сначала встречает X, а затем Y, начинается с узла в поддереве узла X и заканчивается на узле поддерева узла Y, но не в поддереве узла W , где W является непосредственным дочерним элементом узел Y и лежит между X и Y на этих путях.

Следовательно, окончательный ответ можно рассчитать следующим образом:

Count = N * (N – 1) – size_of_subtree(X) * (size_of_subtree(Y) – size_of_subtree(W))

Если Y взять за корень дерева. Тогда size_of_subtree (Y) = N.

Count = N * (N – 1) – size_of_subtree(X) * (N- size_of_subtree(W))

Выполните следующие действия, чтобы решить проблему:

  1. Инициализация массивов subtree_size [], посетил [] и [] check_subtree каждый из размера N + 1. Инициализировать элементы посещенного [] как 0 .
  2. Выполните обход DFS с Y в качестве корневого узла, чтобы заполнить check_subtree [] и subtree_size [] для каждого узла. Check_subtree [] проверяет, содержит ли поддерево текущего узла узел X или нет.
  3. Найдите дочерний элемент (скажем, узел v) Y, который находится на пути от X к Y. Инициализируйте целочисленную переменную, скажем, разность .
  4. Назначьте ( общее количество узлов - subtree_size [v] ) разнице .
  5. Верните (N * (N - 1)) - (subtree_size [A] * (разница)) в качестве ответа.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
#define int long long int
using namespace std;
  
// Maximum number of nodes
const int NN = 3e5;
  
// Vector to store the tree
vector<int> G[NN + 1];
  
// Function to perform DFS Traversal
int dfs(int node, int A, int* subtree_size,
        int* visited, int* check_subtree)
{
    // Mark the node as visited
    visited[node] = true;
  
    // Initialize the subtree size
    // of each node as 1
    subtree_size[node] = 1;
  
    // If the node is same as A
    if (node == A) {
  
        // Mark check_subtree[node] as true
        check_subtree[node] = true;
    }
  
    // Otherwise
    else
        check_subtree[node] = false;
  
    // Iterate over the adjacent nodes
    for (int v : G[node]) {
  
        // If the adjacent node
        // is not visited
        if (!visited[v]) {
  
            // Update the size of the
            // subtree of current node
            subtree_size[node]
                += dfs(v, A, subtree_size,
                       visited, check_subtree);
  
            // Check if the subtree of
            // current node contains node A
            check_subtree[node] = check_subtree[node]
                                  | check_subtree[v];
        }
    }
  
    // Return size of subtree of node
    return subtree_size[node];
}
  
// Function to add edges to the tree
void addedge(int node1, int node2)
{
  
    G[node1].push_back(node2);
    G[node2].push_back(node1);
}
  
// Function to calculate the number of
// possible paths
int numberOfPairs(int N, int B, int A)
{
    // Stores the size of subtree
    // of each node
    int subtree_size[N + 1];
  
    // Stores which nodes are
    // visited
    int visited[N + 1];
  
    // Initialise all nodes as unvisited
    memset(visited, 0, sizeof(visited));
  
    // Stores if the subtree of
    // a node contains node A
    int check_subtree[N + 1];
  
    // DFS Call
    dfs(B, A, subtree_size,
        visited, check_subtree);
  
    // Stores the difference between
    // total number of nodes and
    // subtree size of an immediate
    // child of Y lies between the
    // path from A to B
    int difference;
  
    // Iterate over the adjacent nodes B
    for (int v : G[B]) {
  
        // If the node is in the path
        // from A to B
        if (check_subtree[v]) {
  
            // Calcualte the difference
            difference = N - subtree_size[v];
  
            break;
        }
    }
  
    // Return the final answer
    return (N * (N - 1))
           - difference * (subtree_size[A]);
}
  
// Driver Code
int32_t main()
{
    int N = 9;
  
    int X = 5, Y = 3;
  
    // Insert Edges
    addedge(0, 2);
    addedge(1, 2);
    addedge(2, 3);
    addedge(3, 4);
    addedge(4, 6);
    addedge(4, 5);
    addedge(5, 7);
    addedge(5, 8);
  
    cout << numberOfPairs(N, Y, X);
  
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
  
// Maximum number of nodes
static int NN = (int) 3e5;
  
// Vector to store the tree
static Vector<Integer> []G = new Vector[NN + 1];
  
// Function to perform DFS Traversal
static int dfs(int node, int A, int[] subtree_size,
               int[] visited, int[] check_subtree)
{
    // Mark the node as visited
    visited[node] = 1;
  
    // Initialize the subtree size
    // of each node as 1
    subtree_size[node] = 1;
  
    // If the node is same as A
    if (node == A) 
    {
  
        // Mark check_subtree[node] as true
        check_subtree[node] = 1;
    }
  
    // Otherwise
    else
        check_subtree[node] = 0;
  
    // Iterate over the adjacent nodes
    for (int v : G[node])
    {
  
        // If the adjacent node
        // is not visited
        if (visited[v] == 0
        {
  
            // Update the size of the
            // subtree of current node
            subtree_size[node] += dfs(v, A, subtree_size,
                                      visited, check_subtree);
  
            // Check if the subtree of
            // current node contains node A
            check_subtree[node] = check_subtree[node] | 
                                    check_subtree[v];
        }
    }
  
    // Return size of subtree of node
    return subtree_size[node];
}
  
// Function to add edges to the tree
static void addedge(int node1, int node2)
{
    G[node1].add(node2);
    G[node2].add(node1);
}
  
// Function to calculate the number of
// possible paths
static int numberOfPairs(int N, int B, int A)
{
    // Stores the size of subtree
    // of each node
    int []subtree_size = new int[N + 1];
  
    // Stores which nodes are
    // visited
    int []visited = new int[N + 1];
  
  
    // Stores if the subtree of
    // a node contains node A
    int []check_subtree = new int[N + 1];
  
    // DFS Call
    dfs(B, A, subtree_size,
        visited, check_subtree);
  
    // Stores the difference between
    // total number of nodes and
    // subtree size of an immediate
    // child of Y lies between the
    // path from A to B
    int difference = 0;
  
    // Iterate over the adjacent nodes B
    for (int v : G[B]) 
    {
  
        // If the node is in the path
        // from A to B
        if (check_subtree[v] > 0)
        {
  
            // Calcualte the difference
            difference = N - subtree_size[v];
  
            break;
        }
    }
  
    // Return the final answer
    return (N * (N - 1)) - 
              difference * (subtree_size[A]);
}
  
// Driver Code
public static void main(String[] args)
{
    int N = 9;
  
    int X = 5, Y = 3;
      
    for (int i = 0; i < G.length; i++)
        G[i] = new Vector<Integer>();
    
    // Insert Edges
    addedge(0, 2);
    addedge(1, 2);
    addedge(2, 3);
    addedge(3, 4);
    addedge(4, 6);
    addedge(4, 5);
    addedge(5, 7);
    addedge(5, 8);
  
    System.out.print(numberOfPairs(N, Y, X));
}
}
  
// This code is contributed by sapnasingh4991

Python3

# Python3 program to implement
# the above approach
  
# Maximum number of nodes
NN = int(3e5)
  
# Vector to store the tree
G = []
for i in range(NN + 1):
    G.append([])
  
# Function to perform DFS Traversal
def dfs(node, A, subtree_size, 
        visited, check_subtree):
  
    # Mark the node as visited
    visited[node] = True
  
    # Initialize the subtree size
    # of each node as 1
    subtree_size[node] = 1
  
    # If the node is same as A
    if (node == A):
  
        # Mark check_subtree[node] as true
        check_subtree[node] = True
  
    # Otherwise
    else:
        check_subtree[node] = False
  
    # Iterate over the adjacent nodes
    for v in G[node]:
  
        # If the adjacent node
        # is not visited
        if (not visited[v]):
  
            # Update the size of the
            # subtree of current node
            subtree_size[node] += dfs(v, A,
                                      subtree_size,
                                      visited, 
                                      check_subtree)
  
            # Check if the subtree of
            # current node contains node A
            check_subtree[node] = (check_subtree[node] | 
                                   check_subtree[v])
  
    # Return size of subtree of node
    return subtree_size[node]
  
# Function to add edges to the tree
def addedge(node1, node2):
  
    G[node1] += [node2]
    G[node2] += [node1]
  
# Function to calculate the number of
# possible paths
def numberOfPairs(N, B, A):
  
    # Stores the size of subtree
    # of each node
    subtree_size = [0] * (N + 1)
  
    # Stores which nodes are
    # visited
    visited = [0] * (N + 1)
  
    # Stores if the subtree of
    # a node contains node A
    check_subtree = [0] * (N + 1)
  
    # DFS Call
    dfs(B, A, subtree_size,
        visited, check_subtree)
  
    # Stores the difference between
    # total number of nodes and
    # subtree size of an immediate
    # child of Y lies between the
    # path from A to B
    difference = 0
  
    # Iterate over the adjacent nodes B
    for v in G[B]: