Logo Wy Online Judge

WyOJ

#918. C. 星际信号站 (com)

题目描述

在一个古老的星际网络中,有 $n$ 个信号站,组成了一棵树形结构。每个信号站可以被配置为两种状态之一:状态 $0$ 或状态 $1$。

对于任意两个信号站 $u$ 和 $v$,它们之间的通信路径是由树上连接它们的最短路径上的所有信号站状态组成的序列。路径 $(u,v)$ 的通讯价值定义为该序列的 MEX,即不出现在序列中的最小非负整数。例如: - 序列 $[2,2,1]$ 的 MEX 是 $0$,因为 $0$ 不在序列中。 - 序列 $[3,1,0,1]$ 的 MEX 是 $2$,因为 $0$ 和 $1$ 在序列中,但 $2$ 不在。 - 序列 $[0,3,1,2]$ 的 MEX 是 $4$,因为 $0$、$1$、$2$ 和 $3$ 都在序列中,但 $4$ 不在。

一种配置的总价值是所有可能的信号站对 $(u,v)$(满足 $1 \leq u \leq v \leq n$)的路径通讯价值的总和。

你的任务是确定,通过合理配置每个信号站的状态($0$ 或 $1$),能够获得的最大总价值是多少。

输入格式

第一行包含一个整数 $n$,表示信号站的数量。

接下来的 $n-1$ 行,每行包含两个整数 $a_i$ 和 $b_i$,表示信号站 $a_i$ 和 $b_i$ 之间存在一条直接连接。

输出格式

对于每组数据,输出一行,包含一个整数,表示通过任意配置信号站状态所能得到的最大总价值。

输入输出样例 #1

输入 #1

3
1 2
2 3
1

输出 #1

8

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

15

输入输出样例 #3

输入 #3

10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10

输出 #3

96

说明/提示

在第一组样例中,将信号站 $2$ 配置为状态 $1$,信号站 $1$ 和 $3$ 配置为状态 $0$。考虑所有路径: - $(1,1)$ 的路径值:$1$ - $(1,2)$ 的路径值:$2$ - $(1,3)$ 的路径值:$2$ - $(2,2)$ 的路径值:$0$ - $(2,3)$ 的路径值:$2$ - $(3,3)$ 的路径值:$1$

总价值为 $1 + 2 + 2 + 0 + 2 + 1 = 8$,这是可能的最大值。

数据规模与约定

对于所有数据,保证 $1 \le n \le 2 \times 10^5, 1 \le a _i, b _i \le n, a _i \not = b _i$。保证这些连接构成一棵树。

子任务编号 $n$ 其他限制 分值
$1$ $\le 15$ 无 $20$
$2$ $\le 200$ 无 $15$
$3$ $\le 2000$ 无 $15$
$4$ $\le 2 \times 10^5$ $a _i = i, b _i = i + 1$ $5$
$5$ $\le 2 \times 10^5$ $a _i = 1, b _i = i + 1$ $5$
$6$ $\le 2 \times 10^5$ 无 $40$
题目信息
  • 难度 UKE
  • 控制组 默认组
  • 时间限制 3 s
  • 空间限制 256 MB
  • 数据大小 19.329 MB
提交统计
  • 提交数 3
  • 通过数 3
  • 通过率 100%