UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小青鱼计划越过高高的龙门,成为大青龙。但是仅凭小青鱼的力量是越不过龙门的。所以它和龙王对决,如果赢了,则能获得它的龙行龘龘之力。

对决方式是这样的。龙门旁有一棵 $n$ 个点的无根树 $T$,小青鱼可以从中选择一个 $T$ 的连通子图 $H$。即,选取 $T$ 中的一些边和一些点组成 $H$($H$ 中每条边两端的点都必须被选择),使得任意两个被选取的点可以仅通过被选取的点和边互相到达。

然后,龙王会在 $H$ 中拿走一个最大点独立集,即拿走一个最大的点集,使得任意两点都在 $H$ 中不相邻。

最后,小青鱼会拿走 $H$ 中剩下的点。

对决结果根据二人所拿走的点的个数大小关系决定:点数多者胜,平局也算小青鱼赢。

现在,小青鱼打算选一个 $T$ 的连通子图,使得它能够赢得对决。小青鱼想知道,有多少合法的连通子图满足条件?输出合法方案数,答案对 $998244353$ 取模。

一句话题意: 给定一棵 $n$ 个点的无根树,询问有多少连通子图满足其大小大于等于其最大点独立集的两倍,答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$ ,表示节点数。

接下来 $n-1$ 行,第 $i$ 行两个正整数 $u_i,v_i$($1 \le u_i, v_i \le n$),表示第 $i$ 条边连接的两个节点。

保证输入是一棵树。

输出格式

输出一行一个非负整数,表示求得的答案。

样例一

input

5
1 2
1 3
2 4
2 5

output

6

样例解释一

当小青鱼选择的点集为 $\{1,2\},\{1,3\},\{2,4\},\{2,5\},\{1,2,3,4\},\{1,2,3,5\}$ 时,能赢得赌约。

样例二 $\sim$ 样例四

见下发文件。

数据范围

对于 $100\%$ 的数据,$2 \leq n \leq 5 \times 10^5$。

子任务编号 $n \leq$ 分值
$1$ $10$ $8$
$2$ $20$ $8$
$3$ $50$ $16$
$4$ $200$ $16$
$5$ $5000$ $16$
$6$ $10^5$ $16$
$7$ $5 \times 10^5$ $20$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$