树上会面AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a tree with $N$ vertices numbered $1,2,\dots, N$. For $i=1,2,\dots, N-1$, the $i$-th edge connects vertices $u_i$ and $v_i$.
给定一棵有 $N$ 个顶点的树，顶点编号为 $1,2,\dots, N$。对于 $i=1,2,\dots, N-1$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。AI (CI翻译)
There is one squirrel at each vertex of the tree. The squirrels are trying to hold a meeting as follows.
树的每个顶点上都有一只松鼠。它们打算按以下方式举行一次会议。AI (CI翻译)
- Choose one or more squirrels to participate in the meeting.
- The chosen squirrels consult with each other and choose one vertex of the tree as the venue for the meeting.
- Each of the chosen squirrels moves along the edges of the tree until it reaches the venue.
- 选择一只或多只松鼠参加会议。
- 参加会议的松鼠商量并选择树上的一个顶点作为会议地点。
- 每只参加会议的松鼠沿树边移动，直到到达会议地点。
A squirrel's movement incurs a cost equal to the number of edges it traverses. We define the cost of the meeting as the sum of the movement costs of the chosen squirrels. The squirrels want to choose the venue of the meeting so that the cost of the meeting is minimized.
松鼠移动的代价等于它经过的边数。会议的总代价定义为所有参加会议的松鼠的移动代价之和。松鼠们希望选择会议地点，使会议总代价最小。AI (CI翻译)
There are $2^N-1$ ways to choose one or more squirrels to participate in the meeting. Find the sum, modulo $998244353$, over all of these ways, of the minimum cost of the meeting when the venue is chosen appropriately.
选择一只或多只松鼠参加会议共有 $2^N-1$ 种方式。求对所有这些方式，会议地点经过恰当选择后得到的最小会议总代价之和。答案对 $998244353$ 取模。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$2\le N\le 3\times 10^5$$1\le u_i,v_i\le N$- The given graph is a tree.
- All input values are integers.
$2\le N\le 3\times 10^5$$1\le u_i,v_i\le N$- 给定的图是一棵树。
- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}Output
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
4
1 2
1 3
1 4
21
5
1 2
2 3
3 4
3 5
70
12
1 2
1 3
3 4
4 5
3 6
6 7
6 8
1 9
9 10
10 11
9 12
43813
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。