← 返回题目列表

Codeforces · 1332/F

F. 独立设置

中文机器翻译题面 查看原题

Eric是图论课的老师。今天,Eric 教授独立集和边诱导子图。

给定一个图 $$$G=(V,E)$$$,一个独立集是顶点 $$$V' \subset V$$$ 的子集,这样对于每对 $$$u,v \in V'$$$, $$$(u,v) \not \in E$$$ (即 $$$E$$$ 中没有边连接来自$$$V'$$$)。

边引起的子图由边的子集 $$$E' \subset E$$$ 以及原始图中与子图中至少一条边相关的所有顶点组成。

给定 $$$E' \subset E$$$,表示 $$$G[E']$$$ 边引起的子图,使得 $$$E'$$$ 是子图的边集。以下是这些定义的说明:

为了帮助他的学生熟悉这些定义,他留下了以下问题作为练习:

给定一棵树 $$$G=(V,E)$$$,计算 $$$G$$$ 中除了空边引起的子图 $$$H$$$ 之外的所有子图 $$$w(H)$$$ 的总和,其中 $$$w(H)$$$ 是 $$$H$$$ 中独立集合的数量。形式上,计算$$$\sum \limits_{\emptyset \not= E' \subset E} w(G[E'])$$$。

尽快提供正确答案,向 Eric 表明您比他的学生更聪明。请注意,答案可能很大,您应该输出对 $$$998,244,353$$$ 取模的答案。

输入

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

以下 $$$n-1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \not= v$$$),描述给定树的边缘。

保证给定的边形成一棵树。

输出

输出一个整数,表示所需值对 $$$998,244,353$$$ 取模。

示例

输入 #1

2
2 1

输出 #1

3

输入 #2

3
1 2
3 2

输出 #2

11

注意

对于第二个示例,下面列出了所有独立集。