CF1332F.Independent Set

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$.

Eric 是图论课的老师。今天，Eric 讲授了独立集（independent set）与边导出子图（edge-induced subgraph）的概念。

给定一个图 $G=(V,E)$，一个独立集是指顶点集的一个子集 $V' \subset V$，使得对任意 $u,v \in V'$，均有 $(u,v) \not\in E$（即 $E$ 中不存在连接 $V'$ 中两个顶点的边）。

一个边导出子图由边集的一个子集 $E' \subset E$ 以及原图中至少与 $E'$ 中某条边相关联的所有顶点构成。

对任意 $E' \subset E$，记 $G[E']$ 为以 $E'$ 为边集的边导出子图。以下是这些定义的示意图：

为了帮助学生熟悉这些概念，Eric 留下了如下练习题：

给定一棵树 $G=(V,E)$，计算 $G$ 的所有非空边导出子图 $H$ 的权值 $w(H)$ 之和，其中 $w(H)$ 表示 $H$ 中独立集的个数。形式化地，需计算

$$\sum_{\emptyset \neq E' \subset E} w(G[E']).$$

向 Eric 证明你比他的学生更聪明，请尽快给出正确答案。注意答案可能很大，你应输出答案对 $998\,244\,353$ 取模的结果。

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.

第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$），表示图 $G$ 的顶点数。

接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$，且 $u \neq v$），描述给定树的边。

保证所给的边构成一棵树。

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

输出一个整数，表示所求值对 $998,244,353$ 取模的结果。

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

对于第二个例子，所有独立集如下所示。