Cursed Cactus Challenge (Problem C, CS3233 Midterm Contest 2024, 2024)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
You are given a simple connected graph $G$ with $n$ vertices and $m$ edges. Each vertex $i$ has a value $a_i$. No two edges connect the same pair of vertices. Interestingly, each edge lies in at most one simple cycle.

A simple cycle is a sequence of $k$ distinct vertices $v_1, v_2, \ldots, v_k$, such that there is an edge connecting $v_i$ and $v_{i+1}$ for every $1 \le i \le k - 1$, and also an edge connecting $v_k$ and $v_1$. We note that these $k$ edges lies in the simple cycle  
$v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_k \rightarrow 1$.

Let $S$ be a subset of vertices. We call $S$ an independent set if for all $u, v \in S$ and $u \ne v$, there is no edge connecting the vertices $u$ and $v$. The score $F(S)$ of an independent set $S$ is defined as

$$
F(S) = \left( \sum_{v \in S} a_v \right)^2
$$

Let $\mathcal{I}$ be the set of all possible independent sets in $G$. In other words,

$$
\mathcal{I} = \{ S \subseteq \{1, 2, \ldots, n\} \mid S \text{ is an independent set} \}
$$

Find the following sum, modulo $998\ 244\ 353$.

$$
\sum_{S \in \mathcal{I}} F(S)
$$

# Input

The first line of input contains two integers $n$ ($2 \le n \le 10^5$) and $m$ ($n - 1 \le m \le 2n$).

The second line contains $n$ integers, the $i$-th of which denotes $a_i$ ($1 \le a_i \le 10^8$).

It is guaranteed that the given graph is simple, connected, and each edge lies in at most one simple cycle.

# Output

Output $\sum_{S \in \mathcal{I}} F(S)$, modulo $998\ 244\ 353$.

# Sample Input #1
```
3 2
1 1 1
1 2
2 3
```
# Sample Output #1
```
7
```
# Sample Input #2
```
4 4
3 2 3 3
1 2
2 3
3 4
4 1
```
# Sample Output #2
```
92
```
# Sample Input #3
```
10 12
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
1 8
8 9
9 10
```
# Sample Output #3
```
50520
```

Sample inputs:
3 2
1 1 1
1 2
2 3

4 4
3 2 3 3
1 2
2 3
3 4
4 1

10 12
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
1 8
8 9
9 10

Sample outputs:
7

92

50520

# Solution Analysis

Let $A = \{S_i\}$ be a set of possible independent sets and $B = \{S_i\}$ be another set of possible independent sets. Let’s denote the operation $C = A \times B$ as a convolution of sets where the independent sets in $A$ have no intersection with independent sets in $B$. Namely $C = \{S_A \cup S_B \mid S_A \in A, S_B \in B\}$. I.e. $A = \{\emptyset, \{v_1\}\}, B = \{\emptyset, \{v_2\}\}, C = \{\emptyset, \{v_1\}, \{v_2\}, \{v_1, v_2\}\}$. And $C = A + B$ simply means $C = A \cup B$.

Let’s also denote $F(S_i) = \left(\sum_{v \in S_i} A_v \right)^2$ as mentioned in the question. But let’s also denote $G(S_i) = \sum_{v \in S_i} A_v$.

For each set of independent sets $A$ let’s keep track of 3 values. $cnt(A) = |A|$, $W(A) = \sum_{S \in A} G(S)$, $V(A) = \sum_{S \in A} F(S)$.

We can calculate these values of a set of independent sets $C = A \times B$ given we know the values of $A$ and $B$.

- $cnt(C) = cnt(A) \times cnt(B)$
- $W(C) = W(A) \times cnt(B) + W(B) \times cnt(A)$
- $V(C) = V(A) \times cnt(B) + V(B) \times cnt(A) + 2 \times W(A) \times W(B)$

And for $C = A + B$

- $cnt(C) = cnt(A) + cnt(B)$
- $W(C) = W(A) + W(B)$
- $V(C) = V(A) + V(B)$

Let’s root the graph and construct the DFS tree. Cycles in the graph then simply become a path from $u$ to $v$, where $u$ is an ancestor of $v$, and a back edge from $v$ to $u$. Let us call $u$ the top node of the cycle, $v$ the bottom node and other nodes in the cycle as intermediate nodes of the cycle. Note that since no edge is part of two cycles, a node cannot be an intermediate/bottom node for two cycles, else its parent edge will become a edge in both cycles. Thus each node can be mapped to at most one bottom node.

As such, we can maintain a dp state for each node in the tree: $dp(node, taken?, bottomnodetaken?) = S$ where $S$ is all possible states such involving nodes in the subtree of $node$, where $node$ is taken or not taken (depending on the state) and the node’s mapped bottom node is taken/not taken (depending on the state). This dp state stores the 3 values of $S$ as mentioned above.

For simplicity let $N = \emptyset$ and $V_i = \{v_i\}$. We can then initialise the dp states as such:

- **Node x is a bottom node:**
  - $dp[x][1][0] = dp[x][0][1] = \emptyset$ (Cannot exist)
  - $dp[x][0][0] = N$
  - $dp[x][1][1] = V_x$

- **Node x is not a bottom node:**
  - $dp[x][0][0] = dp[x][0][1] = N$
  - $dp[x][1][1] = dp[x][1][0] = V_x$

For every child of $x$, $y$ we can then perform the transition considering the following cases:

- Node $x$ is a top node for the cycle $y$ is in
- Node $x$ and $y$ are both intermediate/bottom nodes for the same cycle (Note that this should only happen for at most one child)
- Node $y$ is a top node or not part of a cycle

The transitions involve using the operations mentioned above to merge sets of independent sets. For example in the first case, $dp[x][1][1]$ can be updated by multiplying (defined above) the set by $dp[y][0][0]$. The exact transitions are left as an exercise for the reader but should be easy to derive from the state itself.

Thus we can perform this tree dp and eventually get the answer from the dp state of the root. Since there are $O(N)$ states and $O(N)$ transitions (edges) the final time complexity is $\mathcal{O}(N)$.


Special judge (C++ scorer):