Another task about trees

Consider a graph with $N$ vertices, initially devoid of edges. You are tasked with handling $M$ queries, which are of two types:

• Add an edge from vertex v_1 to vertex v_2, ensuring that v_1 and v_2 belong to different trees, and that v_2 is the root of its tree.

• Check if two vertices $a$ and $b$ are part of the same tree.

Solution

We will use the Union-Find data structure with path compression to efficiently manage these operations:

int n, m, l[NMAX];
int calc_leader(int v)
{
    if (l[v] != v)
        l[v] = calc_leader(l[v]);
    return l[v];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        l[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &z, &x, &y);
        if (z == 1)
            l[y] = x;
        else
            if (calc_leader(x) == calc_leader(y))
                printf("YES\n");
            else
                printf("NO\n");
    }
}

Your task is to design a test case that causes this solution to execute for an extended period. Specifically, the number of calls to the function calc_leader should be at least \frac{1}{4} M \log_2 M.