Link: https://qoj.ac/contest/2041/problem/11357

Given a rooted tree with $$$n$$$ nodes, construct a undirected graph as follows:

• For each edge $$$(u, v)$$$ in the tree, add an edge between $$$u$$$ and $$$v$$$.
• For each leaf node $$$u$$$ in the tree, add an edge between $$$u$$$ and the root.

Please calculate the number of spanning trees of the resulting graph, modulo $$$998\,244\,353$$$.

Note that the resulting graph may contain multiple edges between the same pair of nodes.

Constraints:

• $$$n \le 200\,000$$$

Hmmm, the graph is just two nodes connected by $$$5$$$ multiple edges.

Here, the $$$\times x$$$ means there are $$$x$$$ multiple edges between the two nodes.

• Case 0: The graph has only one node, then the answer is $$$\text{dp}[G]$$$.

• Case 1: There are leaves (nodes with degree $$$1$$$) in the graph. We will try to prune the leaves.

  • Let $$$u_i$$$ be such a leaf. We define $$$G'$$$ as the graph with $$$u_i$$$ removed ($$$G' = G - { u_i } - { (u_i, v_i) }$$$).
  • Since the $$$i^\text{th}$$$ edge must be chosen in order for the graph to be connected, we have $$$\text{dp}[G'] = \text{dp}[G] \times a_i$$$.

• Case 2: There are multiple edges in the graph. We will try to twist multiple edges.

  • Let the $$$i^\text{th}$$$ edge be equal to the $$$j^\text{th}$$$ edge, i.e., $$$(u_i, v_i) = (u_j, v_j)$$$.
  • We can compress these two edges into a single edge with value $$$\langle \overline{a_i} a_j + a_i \overline{a_j}, \overline{a_i} \overline{a_j} \rangle$$$.
  • Since we are neither forced to choose nor forced to exclude the edge, $$$\text{dp}[G']$$$ remains unchanged.

• Case 3: There are nodes with degree $$$2$$$. We will try to compress nodes with degree $$$2$$$.

  • Let $$$x$$$ be the node with degree $$$2$$$, and the $$$i^\text{th}$$$ edge $$$(u_i = x, v_i)$$$ and the $$$j^\text{th}$$$ edge $$$(u_j = x, v_j)$$$ be the only two edges incident to node $$$x$$$.
  • We can contract these two edges into a single new edge $$$(v_i, v_j)$$$ with value $$$\langle a_i a_j, \overline{a_i} a_j + a_i \overline{a_j} \rangle$$$.
  • Since we are neither forced to choose nor forced to exclude the edge, $$$\text{dp}[G']$$$ remains unchanged.

• Case 4: Every nodes in the graph has degree at least $$$3$$$.

  • I do not acknowledge a way to reduce the graph even smaller, so we'll have to stop here.

Wait, what? Is the solution incomplete?

Actually, in this problem, we can actually prove that Case 4 will never happen!

Accepted Code: https://qoj.ac/submission/2028367

struct Info { int T, F; };

int Prune(const Info &a) {
    return a.T;
}

Info Twist(const Info &a, const Info &b) {
    return Info {
        .T = (a.F * b.T + a.T * b.F) % mod,
        .F = (a.F * b.F) % mod
    };
}

Info Compress(const Info &a, const Info &b) {
    return Info {
        .T = (a.T * b.T) % mod,
        .F = (a.F * b.T + a.T * b.F) % mod
    };
}

while the queues are not both empty:
    if there are nodes with degree 1:
        let now be such node
        let (u, info) be the only edge incident to node now
        
        /// Case 1, prune leaves ///
        combine the answer with Prune(info)
        
        remove the edge (now, u) from the graph
        if the degree of node u becomes 1 or 2:
            push it to the corresponding queue
    
    else if there are nodes with degree 2:
        let now be such node
        let (u, info_u) and (v, info_v) be the two edges incident to node now
        
        /// Case 3, compress two edges ///
        let info = Compress(info_u, info_v)
        
        if the edge (u, v) already exists:
            /// Case 2, twist multiple edges ///
            let info_uv be the info on edge (u, v)
            info_uv = Twist(info, info_uv)
        else:
            add a new edge (u, v) with info
        
        remove the edges (now, u) and (now, v) from the graph
        if the degree of node u becomes 1 or 2:
            push it to the corresponding queue
        if the degree of node v becomes 1 or 2:
            push it to the corresponding queue

• Series-Parallel Graphs are a special case of General Series-Parallel Graphs, where we start from an edge, and are not allowed to apply the first two operations.
• Planar graphs are $$$K_5$$$-minor-free and $$$K_{3,3}$$$-minor-free.
• General Series-Parallel graphs are $$$K_4$$$-minor-free.
  • Any General Series-Parallel graph is also a Planar graph.
• Outer Planar graphs are $$$K_4$$$-minor-free and $$$K_{2,3}$$$-minor-free.
  • Outer Planar graphs are Planar graphs with an embedding such that all nodes are on the outer face.
  • Any Outer Planar graph is also a General Series-Parallel graph.

Link: https://judge.yosupo.jp/problem/tree_decomposition_width_2

The class of graphs with treewidth at most $$$2$$$ is exactly the same as the class of graphs that do not contain $$$K_4$$$ as a minor, which is also the same as the class of General Series-Parallel Graphs.

Basically, this is an implementation checker of the reduction process.

Given an undirected connected graph with $$$n$$$ nodes and $$$m$$$ edges, there are $$$2^m$$$ ways to assign a direction to each edge.

Please calculate the number of DAGs among these $$$2^m$$$ directed graphs, modulo $$$998\,244\,353$$$.

Constraints:

• $$$n \le 100\,000$$$
• $$$m \le n + 10$$$

Link: https://qoj.ac/contest/313/problem/8460

Given a connected GSPG with $$$n$$$ nodes and $$$m$$$ edges, there are two values $$$w_u$$$ and $$$s_u$$$ on each node $$$u$$$, and two values $$$c_e$$$ and $$$d_e$$$ on each edge $$$e$$$.

You should color each node with either white or silver, each node colored white/silver will contribute $$$w_u$$$/$$$s_u$$$ to the answer, and each edge whose endpoints are colored the same/differently will contribute $$$c_e$$$/$$$d_e$$$ to the answer.

There are $$$Q$$$ modifications, each modification will change the value of $$$w_u$$$, $$$s_u$$$, $$$c_e$$$ or $$$d_e$$$ for some node $$$u$$$ or edge $$$e$$$, and after each modification, you should calculate the maximum possible sum of values among all $$$2^n$$$ possible colorings of the nodes.

Constraints:

• $$$n \le 100\,000$$$
• $$$Q \le 100\,000$$$

Link: https://oj.ntucpc.org/problems/969

There are $$$n$$$ points placed at the vertices of a regular $$$n$$$-gon, numbered $$$0, 1, \ldots, n-1$$$. Initially, there is an edge (a straight line segment) between every $$$i$$$ and $$$(i+1) \bmod n$$$.

For example, when $$$n = 6$$$, the initial state looks like this:

Then there are $$$n-3$$$ operations. In each operation, Sakiko selects a pair of vertices $$$(u_i, v_i)$$$ and draw a straight line segment through $$$u$$$ and $$$v$$$, with the guarantee that this segment does not cross any previously drawn segment (it may intersect at endpoints).

Output $$$n-2$$$ nonnegative integers $$$q_0, q_1, \ldots, q_{n-3}$$$, where $$$q_i$$$ denotes the number of spanning trees of the graph after the $$$i$$$-th operation, taken modulo $$$998\,244\,353$$$.

Constraints:

• $$$n \le 100\,000$$$