把路径内部点的贡献化成 deg(u)-1，将答案转成树上最大点权路径和，再在结尾补上两个端点贡献。
OJ: luogu
题目 ID: P3174
难度:提高+/省选-
标签:树形DP树树的直径推导
日期: 2026-06-21 04:44
题意
在树中选一条简单链作为“主链”。
这条链上的点，以及所有与链上点直接相邻的点，合起来构成一个毛毛虫。 要求最大化这个毛毛虫的点数。
思路
先看一个只用于小数据验证的暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n, m;
vector<int> g[MAXN];
int parent_arr[MAXN];
int vis[MAXN];
int ans;
bool dfs_path(int u, int fa, int target, vector<int> &path) {
path.push_back(u);
if (u == target) {
return true;
}
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) {
continue;
}
if (dfs_path(v, u, target, path)) {
return true;
}
}
path.pop_back();
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// brute.cpp：枚举所有路径，直接统计这条路径及其相邻边带来的点数。
cin >> n >> m;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ans = 1;
for (int s = 1; s <= n; s++) {
for (int t = s; t <= n; t++) {
vector<int> path;
dfs_path(s, 0, t, path);
memset(vis, 0, sizeof(vis));
for (size_t i = 0; i < path.size(); i++) {
int u = path[i];
vis[u] = 1;
for (size_t j = 0; j < g[u].size(); j++) {
vis[g[u][j]] = 1;
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += vis[i];
}
ans = max(ans, cnt);
}
}
cout << ans << '\n';
return 0;
}brute.cpp 枚举路径两端点，找出整条路径，再把路径和路径旁边一层的点都统计进去。
正解的关键是把问题改写成“树上最大路径和”。
考虑一条固定主链上的点 u：
- 如果
u是链内部点，它贡献自己，以及除了链上前后两条边之外的所有相邻点 - 如果
u是链端点，它会比内部点多贡献一个端点方向
整理后可得：
- 内部点贡献
deg(u)-1 - 端点贡献
deg(u)
于是如果我们先给每个点一个基础权值：
w[u] = deg(u)-1
那么任意一条主链的毛毛虫大小，就等于：
- 这条路径上所有
w[u]的和 - 再额外加
2
所以问题变成求树上的最大点权路径和。
下面这张图说明了“路径点 + 挂边点”的来源：
graph G {
rankdir=LR;
A -- B -- C;
A -- X;
B -- Y;
B -- Z;
C -- T;
}
如果 A-B-C 是主链，那么 X,Y,Z,T 这些挂在主链上的点都会被计入答案。
这正是把每个点转成 deg(u)-1 权值后所表达的含义。
于是直接做树上直径式 DP：
down[u]：从u出发往下走的一条最大点权链ans：经过某个点拼出的一条最大点权路径
DP 转移方程
设 best1,best2 是 u 的儿子中最大的两条向下链，则：
最后非单点树答案为 ans + 2，补回主链两个端点的额外贡献。
最后输出：
n=1时答案是1- 否则答案是
ans + 2
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int n, m;
vector<int> g[MAXN];
int w[MAXN];
int down_val[MAXN];
int ans;
void dfs(int u, int fa) {
down_val[u] = w[u];
int best1 = 0;
int best2 = 0;
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) {
continue;
}
dfs(v, u);
int cand = down_val[v];
if (cand > best1) {
best2 = best1;
best1 = cand;
} else if (cand > best2) {
best2 = cand;
}
}
down_val[u] = w[u] + best1;
ans = max(ans, w[u] + best1 + best2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
w[i] = (int) g[i].size() - 1;
}
ans = 0;
dfs(1, 0);
if (n == 1) {
cout << 1 << '\n';
return 0;
}
// 路径上所有点的 (deg-1) 之和，再补回路径两个端点。
cout << ans + 2 << '\n';
return 0;
}复杂度
一次 DFS，时间复杂度
总结
这题最重要的不是直接枚举路径，而是先把一个点在毛毛虫中的贡献表达清楚。
一旦得到 deg(u)-1 这个点权，题目就直接变成了树上最大路径和问题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
