Independent Set
Contest: Codeforces Round 630 (Div. 2)
Difficulty rating: 2500
Tags: dfs and similar, dp, trees

Eric is the teacher of graph theory class. Today, Eric teaches independent set and edge-induced subgraph.

Given a graph $$$G=(V,E)$$$, an independent set is a subset of vertices $$$V' \subset V$$$ such that for every pair $$$u,v \in V'$$$, $$$(u,v) \not \in E$$$ (i.e. no edge in $$$E$$$ connects two vertices from $$$V'$$$).

An edge-induced subgraph consists of a subset of edges $$$E' \subset E$$$ and all the vertices in the original graph that are incident on at least one edge in the subgraph.

Given $$$E' \subset E$$$, denote $$$G[E']$$$ the edge-induced subgraph such that $$$E'$$$ is the edge set of the subgraph. Here is an illustration of those definitions:

In order to help his students get familiar with those definitions, he leaves the following problem as an exercise:

Given a tree $$$G=(V,E)$$$, calculate the sum of $$$w(H)$$$ over all except null edge-induced subgraph $$$H$$$ of $$$G$$$, where $$$w(H)$$$ is the number of independent sets in $$$H$$$. Formally, calculate $$$\sum \limits_{\emptyset \not= E' \subset E} w(G[E'])$$$.

Show Eric that you are smarter than his students by providing the correct answer as quickly as possible. Note that the answer might be large, you should output the answer modulo $$$998,244,353$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$), representing the number of vertices of the graph $$$G$$$.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \not= v$$$), describing edges of the given tree.

It is guaranteed that the given edges form a tree.

Output format:
Output one integer, representing the desired value modulo $$$998,244,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
For the second example, all independent sets are listed below.

Example input:
2
2 1

Example output:
3

Example input:
3
1 2
3 2

Example output:
11

Editorial:
We will call one vertice is colored if and only if it is in the independent set. And a coloring is valid if and only if no two adjacent vertices are both colored.
Therefore, we are asked to calculate the sum of number of valid colorings over all edge induced subgraphs.
To deal with the task, one should notice that for a edge induced subgraph and one valid coloring, we may add those vertices which are removed due to the generation of edge induced subgraph, and remain it uncolored.
Therefore, for a coloring on the original graph $$$G=(V,E)$$$, we could consider removing edges such that it will behave the same with above procedure.
In fact, given a coloring, we can define edge removing is valid if and only if there is no adjacent colored vertice and no isolated vertex is colored. We can actually show that there is almost a one to one corresponding relation betweeen those two procedure except for the case where all vertices remains uncolored and all edges are removed.
Therefore, we can actually solve the following task:
Given a tree $$$G=(V,E)$$$, for any given coloring, define a edge removal is valid if it satisfies above constrains.
And it will suddenly becoming something easy to solve with tree dp. Define $$$dp_{u,0}$$$ be the answer for subtree rooted at $$$u$$$ with additional constraint such that $$$u$$$ is not colored, $$$dp_{u,1}$$$ be the answer where $$$u$$$ is colored and $$$dp_u$$$ be the answer where edges from $$$u$$$ to its children are removed.
Therefore, the dp formula should be
• $$$dp_{u,0}=\prod_{v}(2dp_{v,0}+2dp_{v,1}-dp_v)$$$
• $$$dp_{u,1}=\prod_{v}(2dp_{v,0}+dp_{v,1}-dp_v)$$$
• $$$dp_{u}=\prod_{v}(dp_{v,0}+dp_{v,1}-dp_v)$$$
The answer is easily calculated with those three states.