#3173. 日记和二叉搜索树

日记和二叉搜索树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目限制

2000 ms 1024 M

题目描述

题目背景

日记今天学习了二叉搜索树。二叉搜索树上,对于一个节点,它的左子树上每个点的点权都小于它的点权,它的右子树上每个点的点权都大于它的点权。

题目描述

日记很喜欢二叉搜索树,所以她想把这种性质扩展到一般的树上。

现有一棵以节点 11 为根的树,她给树上每一个节点钦定了一个不同的点权 wiw_i

她认为一对节点 (u,v)(u, v) 是好的,当且仅当 wu<wlca(u,v)<wvw_u < w_{\operatorname{lca}(u, v)} < w_v,其中 lca(u,v)\operatorname{lca}(u, v)u,vu, v 的最近公共祖先。

现在,她想让这棵树尽可能的好,也就是让好的节点对数最多。

额外地,她认为排列是美观的,因此她要求点权 wiw_i 构成一个 1n1 \sim n 的排列。

请输出好的节点对数的最大值。

输入格式

11 行,11 个正整数 nn,代表树有 nn 个节点。

接下来 (n1)(n-1) 行,每行 22 个正整数 u,vu, v,代表树上有一条连接 (u,v)(u, v) 的边。

保证输入构成一棵树。

输出格式

输出 1111 个非负整数,为好的节点对数的最大值。

数据范围

本题设置 50 个测试点,每个测试点 2 分。我们称一个测试点的 idid 为其编号 mod 25\bmod~25。同时,每个测试点满足一些限制,见下:

idid nn \leq 特殊性质
11 1010 rr
22
33 50005000 rr
44
55
66
77
88 3×1043 \times 10^4 rr
99
1010
1111
1212
1313 10610^6 s(1)s(1)
1414
1515 s(2)s(2)
1616
1717 s(3)s(3)
1818
1919 s(4)s(4)
2020
2121 h(10)h(10)
2222
2323 rr
2424
00

特别地,特殊性质 s(x) 代表:对每个节点,其儿子节点个数不超过 xxh(x) 代表:若钦定根节点深度为 11,每个节点的深度为其父节点深度 +1+1,则节点的深度最大值不超过 xxr 代表:数据随机生成,即 ii 的父亲在 [1,i1][1, i-1] 中等概率随机选取。

对全部数据,有 1n1061 \leq n \leq 10^6

输入样例 1

5
1 2
2 3
1 4
4 5

输出样例 1

4

输入样例 2

6
1 2
2 3
2 4
1 5
5 6

输出样例 2

7

样例解释

对于样例 11,此处给出一种存在 44 对好的节点的构造,其中括号前的数为节点编号,括号内的数为权值 wiw_i

T1-sample1.png

可以证明,不存在一种构造使得好的节点的对数 >4>4

样例 22 的一种构造:

T1-sample2.png

暑假集训第一次提高组模拟

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-7-16 14:30
结束于
2024-7-18 6:30
持续时间
40 小时
主持人
参赛人数
34