题目描述

圆滑博士很喜欢最近公共祖先 LCA。给定一棵有 $n$ 个结点的树，根节点为 $1$ 号结点，圆滑博士想求：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}i\times j\times LCA(i,j)$$

$LCA(i,j)$ 表示 $i,j$ 结点的 LCA 的编号。对答案模 998244353。

输入格式

第一行一个整数 $n(1\leq n\leq 3\times 10^5)$。

接下来 $n-1$ 行，每行两个整数 $x,y(1\leq x,y\leq n)$ 表示 $x,y$ 之间有一条连边。

输出格式

一行一个整数表示答案模 998244353。

样例

5
1 2
1 3
2 4
2 5

471

数据范围

对于 $50\%$ 的数据，$n\leq 5000$。

对于 $100\%$ 的数据，满足输入内的约束。