[NowCoder牛客]2021NOIP提高组模拟赛第二场T3——树数树（启发式合并堆）descriptionsolutioncode

146 阅读 0 评论 97 点赞

我是靠谱客的博主甜美睫毛，这篇文章主要介绍[NowCoder牛客]2021NOIP提高组模拟赛第二场T3——树数树（启发式合并堆）descriptionsolutioncode，现在分享给大家，希望可以做个参考。

树数树

description
solution
code

description

【题目描述】
牛牛有一棵 n 个点的有根树，根为 1。
我们称一个长度为 m 的序列 a 是好的，当且仅当：
• $\forall i \in (1, m]$ ， $a_i$ 为 $a_{i-1}$ 的祖先或 $a_{i-1}$ 是 $a_i$ 的祖先
• $1 ≤ ???? < ???? ≤ ????, ????_???? ≠ ????_????$
你需要帮助牛牛求出最长的序列长度

【输入格式】
第一行一个正整数 T，表示数据组数。
对于每组数据第一行一个正整数 n。
接下来 n - 1行，每行两个正整数 u,v，表示树上的一条边

【输出格式】
???? 行，每行一个整数表示每组数据的答案
【样例输入】

复制代码

【样例输出】

复制代码

1
2
7

【数据范围】

对于 100% 的数据， 1 ≤ T ≤ 5， 2 ≤ n ≤ 10⁵， 1 ≤ u, v ≤ n， u ≠ v，输入保证是一棵树

PS : 祖先不仅仅是父亲哦

solution

考场上把祖先当成了父亲，那不就是树的直径吗？？我直接来

好的一遍WA，然后开始怀疑数据——最后好的，打扰了

手玩发现，一个点可以连接其子树的两条链

略微想了一下 $n \leq 3000$ 的 $dp_{i,j}$ 以 $i$ 为根的子树用了 $i$ 及以上的祖先共 $j$ 个，然后最大值 $d p$ ，但是就是没写出来。。。

回归正题，没错一个节点确实可以将子树中的两个序列拼接起来

且处理完父亲节点后就没必要管儿子节点了

所以用堆来维护，点和点的子树所能组成的序列，从下往上合并，每次相当于是子树全合并给父亲，然后父亲选最长的两个子序列进行拼接合并

启发式合并即可

code

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
#define maxn 100005
vector < int > G[maxn];
priority_queue < int > q[maxn];
int id[maxn];
int merge( int x, int y ) {
if( q[x].size() < q[y].size() ) swap( x, y );
while( ! q[y].empty() ) q[x].push( q[y].top() ), q[y].pop();
return x;
}
void dfs( int u, int fa ) {
id[u] = u;
while( ! q[id[u]].empty() ) q[id[u]].pop();
for( auto v : G[u] )
if( v ^ fa ) dfs( v, u ), id[u] = merge( id[u], id[v] );
if( q[id[u]].empty() ) q[id[u]].push( 1 );
else {
int w = q[id[u]].top(); q[id[u]].pop();
if( ! q[id[u]].empty() ) w += q[id[u]].top(), q[id[u]].pop();
q[id[u]].push( w + 1 );
}
}
int main() {
int T, n, u, v;
scanf( "%d", &T );
while( T -- ) {
scanf( "%d", &n );
for( int i = 1;i <= n;i ++ ) G[i].clear();
for( int i = 1;i < n;i ++ ) {
scanf( "%d %d", &u, &v );
G[u].push_back( v );
G[v].push_back( u );
}
dfs( 1, 0 );
printf( "%dn", q[id[1]].top() );
}
return 0;
}