在同一棵树中，选择任意一个点作为根，效果都是相同的。不妨以 \(1\) 为树根，考虑树上 dp，记 \(f_u\) 为以 \(u\) 为根的子树的点数最大值。注意到根节点度数可为 \(1\) 可为 \(4\)，而非根非叶子节点度数必须为 \(4\)。由此可以分两类转移。
-
假设子树中 \(u\) 度数为 \(1\)，则这条边连接的是 \(u\) 与其父节点，故 \(f_u=1\)。
-
假设子树中 \(u\) 度数为 \(4\)，则从 \(u\) 的子节点中 \(v\) 寻找三个最大的 \(f_v\)，即 \(g_1,g_2,g_3\)，故 \(f_u=g_1+g_2+g_3+1\)。需要注意这种情况只在有不少于三个子节点时才能转移。
在每个点处求答案，大体相近，强制取 \(u\) 为选定子树的根节点。
-
假设 \(u\) 的度数为 \(1\)，那么从 \(u\) 的子节点 \(v\) 中找到最大的 \(f_v\) 即可，故 \(ans=f_v+1\)。
-
假设 \(u\) 的度数为 \(4\)，则从 \(u\) 的子节点中 \(v\) 寻找四个最大的 \(f_v\)，即 \(g_1,g_2,g_3,g_4\)，故 \(ans=g_1+g_2+g_3+g_4+1\)。
总时间复杂度 \(O(n)\)。
#include <iostream>
#include <cstdio>
#include <vector>
#define N 1000001using namespace std;vector<int> G[N];
int n,f[N],ans = -1;void dfs( int u , int fa )
{int g[5] = { -1 , -1 , -1 , -1 , -1 };for( auto v : G[u] ){if( v == fa ) continue;dfs( v , u );if( f[v] >= g[1] )g[4] = g[3],g[3] = g[2],g[2] = g[1],g[1] = f[v];else if( f[v] >= g[2] )g[4] = g[3],g[3] = g[2],g[2] = f[v];else if( f[v] >= g[3] )g[4] = g[3],g[3] = f[v];else if( f[v] >= g[4] )g[4] = f[v];}f[u] = 1;if( g[3] >= 0 ){f[u] += g[1] + g[2] + g[3];if( g[4] >= 0 )ans = max( ans , f[u] + g[4] );}if( g[1] > 1 )ans = max( ans , g[1] + 1 );return;
}int main()
{int u,v;cin >> n;for( int i = 1 ; i < n ; i ++ ){cin >> u >> v;G[u].push_back( v );G[v].push_back( u );}dfs( 1 , 0 );cout << ans;return 0;
}
)
底层原理详解)
)
)
