Logo Wy Online Judge

WyOJ

#793. mex

题目背景

${\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\%$ 的数据,无特殊限制。

本题开启捆绑测试。

题目信息
提交统计
  • 提交数 8
  • 通过数 4
  • 通过率 50%