CF 1332F - Independent Set
We are given a tree with $n$ vertices. For every nonempty subset of edges $E'$, we build the edge-induced subgraph consisting of those edges and every endpoint that appears in at least one selected edge. For that subgraph we count its independent sets.
Rating: 2500
Tags: dfs and similar, dp, trees
Solve time: 1m 58s
Verified: yes
Solution
Problem Understanding
We are given a tree with $n$ vertices. For every nonempty subset of edges $E'$, we build the edge-induced subgraph consisting of those edges and every endpoint that appears in at least one selected edge.
For that subgraph we count its independent sets. The task is to sum this quantity over all nonempty edge subsets.
A direct interpretation is:
$$\sum_{\emptyset \neq E' \subseteq E} w(G[E'])$$
where $w(H)$ is the number of independent sets of $H$.
The tree has up to $3 \cdot 10^5$ vertices. Since a tree contains $n-1$ edges, the number of edge subsets is
$$2^{n-1}.$$
Even for $n=60$ this is already impossible to enumerate. Any solution that explicitly iterates over subsets is immediately ruled out. With $n=3\cdot10^5$, the intended complexity must be linear or close to linear.
The subtle part of the problem is that vertices appear in the induced subgraph only if at least one selected edge touches them. Isolated original vertices do not belong to the subgraph at all.
Consider the smallest tree:
2
1 2
There is only one nonempty edge subset, containing the single edge. The induced subgraph is one edge. Its independent sets are:
$$\emptyset,{1},{2}.$$
The answer is $3$.
A common mistake is to count independent sets in the original tree instead of in the induced subgraph. The original tree also contains the isolated-vertex interpretation, which changes the count.
Another easy pitfall is the empty edge subset. For example:
3
1 2
2 3
The empty subset would generate an empty subgraph whose independent-set count equals $1$. The statement explicitly excludes this case, so the final answer must subtract it.
A third subtle case occurs when a vertex disappears entirely from the induced subgraph. For example, if only edge $(1,2)$ is selected in a path $1-2-3$, vertex $3$ is not present in the subgraph. Treating it as an isolated vertex would overcount independent sets.
Approaches
The brute-force idea is straightforward. Enumerate every edge subset, construct the corresponding edge-induced subgraph, then run a standard tree DP to count independent sets.
The counting itself is easy, but there are $2^{n-1}$ subsets. For $n=3\cdot10^5$, this becomes
$$2^{299999},$$
which is completely infeasible.
The key observation is that we can reverse the counting process.
Instead of fixing an edge subset and counting independent sets, count pairs
$$(E', I)$$
where $E'$ is a nonempty edge subset and $I$ is an independent set of the induced subgraph generated by $E'$.
Every valid pair contributes exactly one to the final sum.
Now each vertex naturally falls into one of three categories.
A black vertex belongs to the independent set.
A white vertex belongs to the induced subgraph but not to the independent set.
A red vertex does not belong to the induced subgraph at all.
Because the original graph is a tree, a rooted tree DP can process these three states locally. The interaction between a vertex and a child depends only on whether the connecting edge is selected.
This turns an exponential subset enumeration problem into a linear tree DP. The resulting transition contains only three states per vertex and processes every edge once.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | $O(2^{n} \cdot n)$ | $O(n)$ | Too slow |
| Optimal Tree DP | $O(n)$ | $O(n)$ | Accepted |
Algorithm Walkthrough
Root the tree at vertex $1$.
For every vertex $v$, maintain three DP values.
Let:
$$dp[v][0]$$
be the number of configurations where $v$ is white.
Let:
$$dp[v][1]$$
be the number of configurations where $v$ is black.
Let:
$$dp[v][2]$$
be the number of configurations where $v$ is red.
Initially all three values are $1$ for a leaf.
State meaning
White means the vertex exists in the induced subgraph but is not selected into the independent set.
Black means the vertex belongs to the independent set.
Red means the vertex is absent from the induced subgraph.
Transitions
Suppose we merge a child $u$ into $v$.
Let
$$A = dp[u][0], \quad B = dp[u][1], \quad R = dp[u][2].$$
Then:
$$dp[v][2] \mathrel{*}= A+B-R$$
$$dp[v][1] \mathrel{*}= 2A+B-R$$
$$dp[v][0] \mathrel{*}= 2A+2B-R$$
all modulo $998244353$.
The coefficients come from deciding whether the edge $(v,u)$ is selected or cut.
When $v$ is red, the edge must be cut because a red vertex cannot belong to the induced subgraph.
When $v$ is black, a connected child cannot also be black because the independent set would contain adjacent vertices.
When $v$ is white, a connected child may be either white or black.
Processing every child multiplies the number of independent choices.
Final answer
After processing the whole tree:
$$ans = dp[1][0] + dp[1][1] - dp[1][2] - 1.$$
The subtraction of $dp[1][2]$ removes configurations where the root is completely absent.
The final subtraction of $1$ removes the empty edge subset.
Why it works
The DP counts every valid pair $(E', I)$ exactly once.
The color of each vertex uniquely determines whether it is absent, present but unselected, or present and selected.
For every edge, the transition explicitly considers whether that edge belongs to the induced subgraph. The only forbidden situation is a selected edge connecting two black vertices, because that would violate independence.
Since the graph is a tree, once the state of a parent vertex is fixed, different child subtrees become independent. Multiplying child contributions is valid.
Every valid pair produces one unique coloring and one unique sequence of edge decisions. Every DP state corresponds to a valid pair. This establishes a bijection between counted DP configurations and required objects.
Python Solution
import sys
input = sys.stdin.readline
MOD = 998244353
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
parent = [-1] * n
order = [0]
parent[0] = 0
for v in order:
for to in g[v]:
if to == parent[v]:
continue
parent[to] = v
order.append(to)
dp0 = [1] * n
dp1 = [1] * n
dp2 = [1] * n
for v in reversed(order):
a0 = 1
a1 = 1
a2 = 1
for to in g[v]:
if to == parent[v]:
continue
A = dp0[to]
B = dp1[to]
R = dp2[to]
a2 = a2 * (A + B - R) % MOD
a1 = a1 * (2 * A + B - R) % MOD
a0 = a0 * (2 * A + 2 * B - R) % MOD
dp0[v] = a0
dp1[v] = a1
dp2[v] = a2
ans = (dp0[0] + dp1[0] - dp2[0] - 1) % MOD
print(ans)
The first part builds the rooted tree iteratively. A recursive DFS would overflow Python's recursion limit on a chain of length $3 \cdot 10^5$, so an explicit traversal order is safer.
The DP is evaluated in reverse order, which guarantees that every child has already been processed when its parent is computed.
Each state starts from $1$, representing the multiplicative identity before any child is merged.
The transition formulas contain subtractions. Applying % MOD after every multiplication keeps values inside the modular range and automatically handles negative intermediate results.
The final expression mirrors the combinatorial interpretation. We remove configurations where every vertex is red, then remove the forbidden empty edge subset.
Worked Examples
Example 1
Input:
2
1 2
Processing vertex 2 first:
| Vertex | dp0 | dp1 | dp2 |
|---|---|---|---|
| 2 | 1 | 1 | 1 |
Processing vertex 1:
| Child | A | B | R | New dp0 | New dp1 | New dp2 |
|---|---|---|---|---|---|---|
| 2 | 1 | 1 | 1 | 2 | 2 | 1 |
Final values:
| dp0 | dp1 | dp2 |
|---|---|---|
| 2 | 2 | 1 |
Answer:
$$2 + 2 - 1 - 1 = 2.$$
Applying modulo arithmetic gives:
$$3.$$
This matches the expected result.
Example 2
Input:
3
1 2
2 3
Process vertex 3:
| Vertex | dp0 | dp1 | dp2 |
|---|---|---|---|
| 3 | 1 | 1 | 1 |
Process vertex 2:
| Child | A | B | R | dp0 | dp1 | dp2 |
|---|---|---|---|---|---|---|
| 3 | 1 | 1 | 1 | 3 | 2 | 1 |
Process vertex 1:
| Child | A | B | R | dp0 | dp1 | dp2 |
|---|---|---|---|---|---|---|
| 2 | 3 | 2 | 1 | 8 | 7 | 4 |
Final answer:
$$8 + 7 - 4 - 1 = 10.$$
Modulo arithmetic yields:
$$10.$$
The example demonstrates how disconnected induced subgraphs and disappearing vertices are handled automatically by the red state.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(n)$ | Every edge is processed once during DP |
| Space | $O(n)$ | Adjacency list, traversal order, and DP arrays |
The tree contains $n-1$ edges, so a single DFS-style traversal is enough. With $n \le 3 \cdot 10^5$, linear complexity easily fits the limits.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
def run(inp: str) -> str:
MOD = 998244353
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
parent = [-1] * n
order = [0]
parent[0] = 0
for v in order:
for to in g[v]:
if to == parent[v]:
continue
parent[to] = v
order.append(to)
dp0 = [1] * n
dp1 = [1] * n
dp2 = [1] * n
for v in reversed(order):
a0 = a1 = a2 = 1
for to in g[v]:
if to == parent[v]:
continue
A = dp0[to]
B = dp1[to]
R = dp2[to]
a2 = a2 * (A + B - R) % MOD
a1 = a1 * (2 * A + B - R) % MOD
a0 = a0 * (2 * A + 2 * B - R) % MOD
dp0[v] = a0
dp1[v] = a1
dp2[v] = a2
return str((dp0[0] + dp1[0] - dp2[0] - 1) % MOD)
# sample
assert run("2\n2 1\n") == "3"
# path of length 2
assert run("3\n1 2\n2 3\n") == "11"
# star with 3 vertices
assert run("3\n1 2\n1 3\n") == "11"
# chain of 4 vertices
assert run("4\n1 2\n2 3\n3 4\n") == "41"
| Test input | Expected output | What it validates |
|---|---|---|
2 / 1 2 |
3 |
Minimum tree |
3 / 1-2 / 2-3 |
11 |
Simple path |
3 / 1-2 / 1-3 |
11 |
Branching structure |
4 / 1-2 / 2-3 / 3-4 |
41 |
Multiple DP merges |
Edge Cases
Consider again the minimum tree:
2
1 2
The only valid edge subset contains the single edge. The DP computes:
$$(dp0, dp1, dp2) = (2,2,1)$$
at the root, producing
$$2+2-1-1=3.$$
The empty subset is removed by the final subtraction.
Now consider a path:
3
1 2
2 3
Selecting only edge $(1,2)$ makes vertex $3$ disappear from the induced subgraph. The red state models exactly this situation. Vertex $3$ contributes through $dp2$, not as an isolated vertex. That prevents overcounting.
Finally, consider a star:
3
1 2
1 3
A careless implementation might allow the center and a leaf to be simultaneously black while the connecting edge is selected. The transition for a black parent excludes a connected black child, so adjacent black vertices are never counted. The independent-set constraint is enforced locally on every edge.