Guni
============
Guni is one of the beautiful and practical algorithms in trees that solves a wide range of problems. In this problem, we have a Guni (an arbitrary data structure) where in each operation we can either remove a vertex of the tree from it or add a vertex to it. Our tree is rooted, and the goal is for each of the :math:`n` subtrees of the tree to have been placed alone in the Guni at least once, while keeping the total number of operations bounded by :math:`O(n \lg(n))`.

Application
---------
In many problems, a "guni" can be used (several examples are given in this chapter's exercises). But to better clarify this concept and its importance, we'll solve an example together. In this problem, we have a rooted tree where each vertex has a color. For every subtree, we want to calculate and output the number of distinct colors. Assume you know the guni problem's solution and try to solve this problem using it.

To solve this problem, we use a data structure that can:
1. Add a vertex
2. Remove a vertex
3. Return the count of distinct colors

This data structure can be a simple array where:
- When adding a vertex, we increment the corresponding color's cell by 1
- When removing a vertex, we decrement the corresponding color's cell by 1
- We simultaneously maintain a distinct color counter (i.e., if a color's count changes from 0 to 1 when added, we increment the counter; if it changes to 0 when removed, we decrement the counter)

All three operations in this data structure run in :math:`O(1)` time.

Now we use the guni algorithm (whose implementation details we currently don't know). We process all subtrees once in this data structure, record their answers, then print the results.

Algorithm
----------
The idea of the sack is similar to the heavy-light separation idea introduced in the chapter on Lowest Common Ancestor (LCA). (For a reminder, you can refer to Section 10.2). Our goal is to perform operations on each vertex proportional to the number of its light edges in the path to the root. That is, the total number of deletions and additions of vertex 
:math:`v` 
to the sack during all operations should be 
:math:`O(light_v)`. 
From Section 10.2, we recall that 
:math:`light_v \le \lg(n)`, 
so if we succeed in this, the total operations across all vertices will be 
:math:`O(n \lg(n))`.

We implement the algorithm as a recursive function. This function takes an input vertex, starts with an empty sack, places all subtrees rooted under this vertex into the sack once, then returns the sack containing all vertices of its subtree. Implementing this function is trivial for a leaf node and runs in constant time. For non-leaf vertices, we proceed recursively. First, we execute the function on all light-edge children and empty the sack after each execution. Next, we execute the function on the heavy-edge child of this vertex **without emptying the sack**, then re-add the light-edge children to the sack. Now the entire subtree is in the sack. We retrieve the answer for the input vertex from the data structure and terminate the function.

During execution, all children of the heavy-edge vertex are only added to or removed from the sack as required by the recursive function, while light-edge children are removed once and re-added once by the main function. The input vertex itself is also added once at the end. It can be observed that the total number of additions and removals for any vertex 
:math:`v` 
is exactly 
:math:`2 light_v + 1`. 
Additionally, the runtime of the algorithm is proportional to the number of sack operations, and both—as explained above—are 
:math:`O(n \lg(n))`.

Implementation
---------------

This section discusses the implementation of graph algorithms. Below is an example code block for checking bipartiteness:

.. code-block:: python
   :linenos:

   def is_bipartite(g):
       # In this problem, we assume the graph is undirected
       color = {}
       for node in g.nodes():
           if node not in color:
               queue = [node]
               color[node] = 0
               while queue:
                   v = queue.pop(0)
                   for neighbor in g.neighbors(v):
                       if neighbor in color:
                           if color[neighbor] == color[v]:
                               return False
                       else:
                           color[neighbor] = 1 - color[v]
                           queue.append(neighbor)
       return True

.. figure:: images/bipartite_graph.png
   :align: center
   :width: 60%

Another example with adjacency matrix representation:

.. code-block:: python
   :linenos:

   def has_cycle(matrix):
       # Detects cycles in undirected graphs using DFS
       visited = [False] * len(matrix)
       for i in range(len(matrix)):
           if not visited[i]:
               stack = [(i, -1)]
               while stack:
                   node, parent = stack.pop()
                   visited[node] = True
                   for j in range(len(matrix[node])):
                       if matrix[node][j]:
                           if not visited[j]:
                               stack.append((j, node))
                           elif j != parent:
                               return True
       return False

Key points to remember:

1. Always handle disconnected graphs
2. Choose appropriate data structures based on graph density
3. Consider edge cases like empty graphs and single-node graphs

.. code-block:: cpp

    const int M = 1e5 + 5;
    vector<int> g[M];
    int sz[M]; // andaaze zirderakht har ras, baraaye tashkhis yaal haaye sabok va sangin
    
    void add_to_gooni(int v) {
      // piade sazi motenaseb ba masale raa injaa gharaar dahid
    }
    void remove_from_gooni(int v) {
      // piade sazi motenaseb ba masale raa injaa gharaar dahid
    }
    void compute_answer() {
      // piade sazi motenaseb ba masale raa injaa gharaar dahid
    }

    void add_subtree(int v, int p){
        add_to_gooni(v);
        for(int u: g[v])
            if(u != p)
                add_subtree(u, v);
    }
    void remove_subtree(int v, int p){
        remove_from_gooni(v);
        for(int u: g[v])
            if(u != p)
                add_subtree(u, v);
    }
    
    void dfs(int v, int p){
        int mx = -1, bigChild = -1;
        for(int u : g[v]) {
          if(u != p && sz[u] > mx) {
            mx = sz[u];
            bigChild = u;
          }
        }
        for(int u : g[v]) {
          if(u != p && u != bigChild) {
            dfs(u, v); // javaabe farzand haye sabok ra mohaasebe mikonim
            remove_subtree(v, p); // sepas aan haa raa paak mikonim
          }
        }
        if(bigChild != -1)
            dfs(bigChild, v);  // farzande sangin raa paak nemikonim
        for(auto u : g[v]) {
          if(u != p && u != bigChild)
            add_subtree(u, v); // farzand haye sabok ra mojadadan bar migardaanim
        }
        compute_answer(); // hame zirderakht v dar gooni ast, javabash ra hesab mikonim
    }

.. note::  
   توجه کنید که در این پیاده‌سازی، باید گراف را ورودی بگیرید و مقادیر آرایه  
   ``sz``  
   را با یک **DFS** دیگر پر کنید که در این‌جا به آن اشاره نکردیم.  

.. code-block:: python  
   :linenos:  
   
   # درخت DFS ریشه‌دار بسازید  
   def dfs(u, parent):  
       sz[u] = 1  # اندازه زیردرخت اولیه  
       for v in graph[u]:  
           if v != parent:  
               dfs(v, u)  
               sz[u] += sz[v]  # افزودن اندازه زیردرخت فرزند  

.. image:: images/dfs_tree.png  
   :align: center  

**توضیحات:**  
- در خط ۴، حلقه روی همسایه‌های رأس ``u`` اجرا می‌شود.  
- شرط ``v != parent`` از بازگشت به والد جلوگیری می‌کند.  
- در خط ۶، اندازه زیردرخت فرزند به والد اضافه می‌شود.  

**نکته:**  
الگوریتم فوق اندازه زیردرخت هر رأس را در آرایه ``sz`` ذخیره می‌کند. برای پر کردن این آرایه با روش‌های دیگر (مثلاً BFS)، نیاز به تغییر الگوریتم دارید.