Simple Graph Theory and Construction

A

Consider vertices with weight 2 as adding one to vertices with weight 1. Thus the problem is split into two parts: constructing the tree and adding one to vertices.

In the first part, constructing the tree as balanced as possible is beneficial, as will be shown in the second step.

Construction:

Process DFS(father, ch, u, size):
    if size == 0 then return
    son[father][ch] = u
    size = size - 1
    DFS(u, 0, v, size / 2)
    DFS(u, 1, v', size - size / 2)

Then consider distributing the added ones. Specifically, note that adding one to a node does not affect the balance within its subtree. So we greedily assign from top to bottom: first add one to itself, then give one to the smaller subtree, then split the rest equally. Because the tree is as balanced as possible, the difference between each node and its sibling is at most one, satisfying this greedy allocation.

B

Recursively construct. Suppose for each subtree $v_i$ of node $u$, we already have an answer array $array[v] = {v_{state_1}, v_{state_2}, v_{state_3}, \dots}$. Consider the tuples:

$$\langle i, j, k, \dots \rangle = (v^{(1)}{state_i}, v^{(2)}{state_j}, v^{(3)}_{state_3}, \dots)$$

Go through the following process:

i: 1 -> x
    then j: 1 -> 2
i: x -> 1
    then j: 2 -> 3
...
    then j: y-1 -> y
        then k: 1 -> 2
i: 1 -> x
    then j: y -> y-1
                        ...

Then $len(array[u]) = \prod len(array[v_i])$.

C

Transform the problem: treat each given pair as an edge. We need to pair edges such that each pair shares a common vertex.

Consider the case of a connected graph. If it is a tree, we use induction: In a subtree rooted at $u$, pair edges within the subtree. If the subtree has an even number of edges, they can be perfectly matched. If odd, there will be one remaining edge connecting $u$ to its parent, which will be paired with another such edge from a sibling at the parent level.

For a general graph, the same holds because on the DFS spanning tree, non-tree edges are back edges, which can be considered together at the parent.

D

For the first $n/2$ assignments, we ensure no one beats another. For the last $n/2$ assignments, we ensure each earlier one beats a later one, and every assignment in the latter half beats all in the former half. This yields:

$$\frac{n}{2} \cdot \frac{(1+\frac{n}{2})\cdot\frac{n}{2}}{2} = \frac{n^3}{16}$$

total comparisons, meeting the requirement.

E

Use equal-area transformation.

First note that $k \mid n \times m \times 2$, and set $x = \frac{n \times m \times 2}{k}$.

If $n \ge x$, set base = $x$ and height = $1$.

If $n < x$, set base = $n$, then height = $\frac{x}{n}$, which may be fractional. So we transform to integer coordinates. Initially the triangle's base is parallel to the axes:

Then lift $(0,0)$ by one point, making the base slanted:

The top-right point can slide on the gray line. Since the line's slope is $1/n$, moving right by one integer increases $y$ by $1/n$. Adjust $y$ to $\lceil x/n \rceil$:

Here $t$ is the leftward slide: $t = (\lceil x/n \rceil - x/n) \times n$, which is less than $n$. The triangle's area is $x/2$, as required.

F

For even side lengths, construct as follows:

<--even-->
1111111111
1*1*1*1*11
11+1*1+1+1
1*1*1*1*11
1111111111

If both length and width are odd, using the above yields a situation like 11*11. Replace one asterisk with a plus:

1 1 1 1 1 1 1 1 1
1 * 1 * 1 * 1 * 1
1 1 + 1 * 1 * 1 1
1 * 1 * 1 * 1 * 1
1 1 * 1 + 1 * 1 1
1 * 1 * 1 * 1 * 1
1 1 * 1 * 1 + 1 1
1 * 1 * 1 * 1 * 1
1 1 1 1 1 1 1 1 1

G

Simple max flow: bipartite matching. Each left node connects to its factors on the right with capacity 1, and each right node connects to a super sink with capacity 1.

H

Minimum cut. Split each node $x$ into three nodes $x_1, x_2, x_3$ with edges:

$$(x_1) \xrightarrow{1} (x_2) \xrightarrow{\infty} (x_3)$$

For incoming edges to $x$:

• If a checkpoint is at $x$, the edge goes to $x_1$.
• Otherwise, it goes to both $x_3$ and $x_1$.

For outgoing edges from $x$:

• If checkpoint at $x$, the edge starts from $x_2$.
• Otherwise, from $x_3$.

Each edge has a unique start and end, so the graph is well-defined. Then run min-cut. Pay attention to constant factors; some people's Dinic may be too slow.

I

Consider a strongly connected component (SCC). It can loop indefinitely within itself if and only if there exists a cycle with non-zero total weight. So we can run DFS on the SCC to find such a cycle.

Then a SCC can contribute to infinite loops if either it has an internal infinite cycle or it can reach another SCC that does. So simply run Tarjan.

J

Represent each arc as a vector:

$$\vec{a} = \begin{bmatrix} r \ r \end{bmatrix}$$

We need to assign signs to the two components of each vector so that the sum is zero.

For smooth connections, $n$ must be even (alternating directions).

Proof idea: The parity of turning direction does not change under transformation, so each direction must appear an odd number of times.

We need a selection of $r_i$ such that:

$$\sum_{\text{selected}} r_i = \frac{\sum r_i}{2}$$

Since we need two sets (for x and y components), we need at least 4 different selection ways. So we do a DP count: $dp[0/1][i][x]$ = number of ways to choose an odd/even number of arcs among firstt $i$ with sum $x$, capped at 4.

Then check if $dp[1][n][\sum r/2] \ge 4$.

K

Use layered graph + shortest path.

ex

From the previous data structure problem, using matrices for checking matching is not wrong but needs modification. The matrix can determine if a bracket segment is valid, but not if it's legal (e.g., )(, ][, }{). So first check validity, then compute matrix product for hashing.

Let $dp[i]$ be the position where the $i$-th bracket is matched (or blocked by an unmatched bracket). For an interval $(l, r)$, $\min_{l \le i \le r} dp[i] \le r$ determines if the segment is valid.