TREESUBS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

DFS

PROBLEM:

You are given a graph with N vertices and N+1 edges.
It may have multi-edges.
Count the number of spanning trees of the graph.

EXPLANATION:

If the graph is not connected to begin with, clearly there cannot be a spanning tree; so we immediately answer 0.
We thus only need to analyze the case where the graph is connected.

Since we have a connected graph, it definitely has at least one spanning tree.
Take any one such spanning tree (which can be found using DFS, for example).
This spanning tree will have N-1 edges, which means we have two extra edges with us.

Note that adding any single extra edge to the existing spanning tree will create exactly one cycle - that being the added edge itself, along with the path between its endpoints in the spanning tree.

So, we have with us two cycles (there might be more, as we’ll see later - but we work with just these two for now).
There are now a couple of cases.

First, it is possible that the two cycles we have don’t share any edges at all.
In this case, these two cycles are the only cycles in the entire graph.

A spanning tree cannot include any cycles; which means any spanning tree of the graph must exclude exactly one edge from the first cycle and one edge from the second.
Since the cycles don’t intersect, it doesn’t really matter which edge is excluded from each - that is, all choices are equally viable, since deleting any one edge from each cycle will not disconnect the graph and after two deletions we’ll have a tree.

Thus, in this case, the answer is simply the product of the cycle lengths.

Second, it’s possible that the cycles do intersect at some edges.

Let’s call the two cycles C_1 and C_2, for convenience.
In this case, we can partition the edges of the graph into four classes:

  • Edges that belong to neither C_1 nor C_2.
  • Edges that belong to C_1 but not C_2.
  • Edges that belong to C_2 but not C_1.
  • Edges that belong to both C_1 and C_2.

We’ll call these type-1,2,3,4 edges, respectively.

Observe that type 1 edges do not lie on any cycle at all, so definitely cannot be deleted.

Our two existing cycles are C_1 and C_2.
C_1 is formed by the union of type 2 and type 4 edges, while C_2 is formed by the union of type 3 and type 4 edges.
However, in this case we in fact have one more cycle: the type 2 and type 3 edges together themselves will form a cycle.
(This should become clear if you try drawing out a few examples on paper.)

We thus have exactly three cycles in the graph; and our two edge deletions must ensure we break all three of them in order to have a spanning tree.

Each cycle is obtained as the union of two classes of edges (among types 2, 3, 4).
Suppose we delete some type-2 edge.
This would in the only remaining cycle being the union of type-3 and type-4 edges; so we would have to delete one among them to break this cycle.
On the other hand, if we don’t delete any type-2 edge, we are then forced to delete both one type 3 and one type 4 edge (if we don’t delete a type 3 edge for example, the union of types 2 and 3 would remain a cycle.)

Thus, if there are x, y, z edges of types 2, 3, 4 respectively, the number of choices we have is exactly

xy + yz + xz

since we need to choose one edge each from two different classes.

All that remains is to implement the above solution.

Once you find any spanning tree, the remainder is almost brute force.
There are two extra edges, each of them affect only the edges along the path in the tree defined by their endpoints.
So, you only need to be able to traverse some path of the tree; which is easy enough to do in linear time (by storing parents, for example.)
In particular, if the spanning tree is constructed via DFS, the paths that need to be traversed will be ancestor-descendant paths so you don’t even need to worry about LCA and whatnot.

Once all edges have been marked appropriately for each cycle, the rest is simple.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int test = 0;
    
    int t; cin >> t;
    while (t--) {
        ++test;
        int n; cin >> n;
        vector adj(n, vector<array<int, 2>>());
        vector<array<int, 2>> edges;
        for (int i = 0; i < n+1; ++i) {
            int u, v; cin >> u >> v;
            adj[--u].push_back({--v, i});
            adj[v].push_back({u, i});
            edges.push_back({u, v});
        }

        vector par(n, -1), mask(n, 0), dep(n, 0);
        int val = 1;
        array<ll, 4> ct{};
        auto dfs = [&] (const auto &self, int u) -> void {
            for (auto [v, id] : adj[u]) {
                if (par[u] == id) continue;

                if (dep[v] == 0) {
                    dep[v] = dep[u] + 1;
                    par[v] = id;
                    self(self, v);
                }
                else if (val <= 2 and dep[v] < dep[u]) {
                    int x = u;
                    while (x != v) {
                        mask[x] |= val;
                        x ^= edges[par[x]][0] ^ edges[par[x]][1];
                    }
                    ++ct[val];
                    ++val;
                }
            }
        };
        dep[0] = 1;
        dfs(dfs, 0);

        if (ranges::count(dep, 0) > 0) cout << 0 << '\n';
        else {
            for (int x : mask) ++ct[x];
            cout << ct[1]*ct[2] + ct[1]*ct[3] + ct[2]*ct[3] << '\n';
        }
    }
}
1 Like