樹數樹

• description
• solution
• code

description

【題目描述】
牛牛有一棵 n 個點的有根樹，根為 1。
我們稱一個長度為 m 的序列 a 是好的，當且僅當：
? $?i\in (1,m]$， $a_i$為 $a_{i?1}$的祖先或 $a_{i?1}$是 $a_i$ 的祖先
? $?1\le i<j\le m,a_i=a_j$
你需要幫助牛牛求出最長的序列長度

【輸入格式】
第一行一個正整數 T，表示數據組數。
對于每組數據第一行一個正整數 n。
接下來 n - 1行，每行兩個正整數 u,v，表示樹上的一條邊

【輸出格式】
𝐓 行，每行一個整數表示每組數據的答案
【樣例輸入】

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

【樣例輸出】

7

【數據范圍】

對于 100% 的數據， 1 ≤ T ≤ 5， 2 ≤ n ≤ 10⁵， 1 ≤ u, v ≤ n， u ≠ v，輸入保證是一棵樹

PS : 祖先不僅僅是父親哦

solution

考場上把祖先當成了父親，那不就是樹的直徑嗎？？我直接來

好的一遍WA，然后開始懷疑數據——最后好的，打擾了

手玩發現，一個點可以連接其子樹的兩條鏈

略微想了一下$n\le 3000$的$d{p}_{i,j}$以$i$為根的子樹用了$i$及以上的祖先共$j$個，然后最大值$dp$，但是就是沒寫出來。。。

回歸正題，沒錯一個節點確實可以將子樹中的兩個序列拼接起來

且處理完父親節點后就沒必要管兒子節點了

所以用堆來維護，點和點的子樹所能組成的序列，從下往上合并，每次相當于是子樹全合并給父親，然后父親選最長的兩個子序列進行拼接合并

啟發式合并即可

code

#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( "%d\n", q[id[1]].top() );}return 0; }

總結

以上是生活随笔為你收集整理的[NowCoder牛客]2021NOIP提高组模拟赛第二场T3——树数树（启发式合并堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。