题目背景
${\Huge{\bullet}}{\color{Orange}{\texttt{sumomosun}}}\space\space\space\space$${\small {\color{Gray}{回复于 56 分钟前}} } $$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space$${\small {\color{Gray}{举报 回复}} } $
mex:百度词条 是墨西哥和军用交换机的意思
@zxh_qwqmex是max吧
本jiruo看不懂$dalao$求解
题目描述
给定一颗 $n$ 个节点的无根树。你可以对每个节点赋一个 $0$ 或 $1$ 的权值。将一条路径的价值定义为这条路径上所有点权的 $\text{mex}$,求在最优染色方案下所有路径的价值和的最大值($(u,v)$ 和 $(v,u)$ 视作同一条边)。
注:$\text{mex}$ 是指一个数组中最小的不属于该数组的非负整数。如 $\text{mex}\{1,2,4\}=0$,$\text{mex}\{0,1,2\}=3$。
输入格式
第一行一个整数 $n$,代表树的节点个数。
接下来 $n-1$ 行,每行输入两个整数 $u,v$,代表存在一条连接 $u$ 和 $v$ 的边。
输出格式
一行一个整数,代表答案。
输入输出样例 #1
输入 #1
3
1 2
2 3
输出 #1
8
说明/提示
样例解释
我们可以将节点 $2$ 染成 $1$,节点 $1,3$ 染成 $0$。此时,所有路径的价值如下:
- $(1,1)$ 的价值为 $1$
- $(1,2)$ 的价值为 $2$
- $(1,3)$ 的价值为 $2$
- $(2,2)$ 的价值为 $0$
- $(2,3)$ 的价值为 $2$
- $(3,3)$ 的价值为 $1$
价值之和为 $8$。
数据范围
$1\le n\le 2\times10^5$。
对于 $20\%$ 的数据,$1\le n\le 10^3$。
对于另外 $40\%$ 的数据,$1\le n\le 2\times10^4$。
对于剩余 $40\%$ 的数据,无特殊限制。
本题开启捆绑测试。
