ABC 447 F - Centipede Graph

RookieSama_

公告

欢迎来到小破站ようこそ私のブログへ！

Learn Morea

标签

1109 字

6 分钟

ABC 447 F - Centipede Graph

2026-03-01

题解

树形dp

F - Centipede Graph #

题目大意：#

给你一颗树形结构的图, 现在让你找出满足和蜈蚣一样的最长长度

解题思路：#

通过观察可以发现：蜈蚣的躯干是由以下组成的:
- 头，尾巴：连接三个顶点
- 身体：连接四个顶点
我们只需要查找身体 + 头尾的最长组合就行了
要求 3 $\leq$ 头，4 $\leq$ 身体;
$du[u]$ 表示 u 点的度数
我们用 $dp[u]$ $d p [u]$ 表示 以 u 为端点 满足躯干度数要求的最长路径的节点数
- 1. 如果 $du[u] \leq 2$ 无法成为节点直接排除 $dp[u] = 0$
- 1. 如果 $du[u] == 3$ 那么节点u 只能作为端点 $dp[u] = 1$ (仅自己作为端点)
  - 答案更新：如果 child 非空，则可连接在子路径后 $ans = max(ans,child[0] + 1)$
  - 否则单独成路径 $ans = max(ans, 1)$
- 1. 如果 $du[u] \geq 4$ 那么节点 u 能作为端点或者中间节点
  - 2.1: 如果 u 作为中间节点，则取子节点中最长的两条路径拼接，要求 $child.size() \geq 2$ , $ans = max(ans,1 + child[0] + child[1])$
  - 2.2: 如果 u 作为端点, 那么只能拼接子树中最长路径，同时 $dp[u] = max(dp[u],1 + child[0])$
  - 2.3: 自己单独作为路径： $ans = max(ans, 1)$
最后返回 $dp[u]$ (以 u 点作为最长的链)
答案就是 $ans$

易错点：#

本题可能很难直接通过查找最长路径解决题目，可能会省略一些路径（其实我没找到反例，前面也是用该方法一直wa）

错误代码样例：#

直接通过查找最长能够实现的路径，特殊判断两个端点（不知道为啥wa，有机会取对拍一下）

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
using PII = pair<int, int>;
5
#define int long long
6
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
7
const int N = 2e5 + 10, mod = 998244353;
8

9
int n, m;
10
int du[N];// 无向图度
11
int h[N], e[N * 2], ne[N * 2], idx;
12
int st[N], core[N]; // core 用于判断是否是核心点
13
int max_dist, far_node;
14
vector<int> p;
15

16
void init(){
17
    idx = 0;
18
    max_dist = 0, far_node = 0;
19
    for(int i = 0; i <= n; i++) {
20
        h[i] = -1;
21
        du[i] = 0;
22
        st[i] = 0;
23
        core[i] = 0;
24
    }
25
}
26

27
void add(int a, int b){
28
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
29
}
30

31
void dfs(int u, int fa, int dist){
32
    st[u] = 1;
33
    p.push_back(u);
34
    if(dist > max_dist){
35
        max_dist = dist;
36
        far_node = u;
37
    }
38
    for(int i = h[u]; ~i; i = ne[i]){
39
        int j = e[i];
40
        if(j != fa && core[j]){
41
            dfs(j, u, dist + 1);
42
        }
43
    }
44
}
45

46
int check(int u){
47
    for(int i = h[u]; ~i; i = ne[i]){
48
        if(du[e[i]] == 3){
49
            return 1;
50
        }
51
    }
52
    return 0;
53
}
54

55
void solve(){
56
    cin >> n;
57
    init();
58
    vector<PII> edges;
59
    for(int i = 1; i < n; i++){
60
        int u, v;
61
        cin >> u >> v;
62
        add(u, v), add(v, u);
63
        du[u]++, du[v]++;
64
        edges.push_back({u, v});
65
    }
66

67
    int ans = 1;
68

69
    for(auto& i: edges){// 处理 只有两个点的情况
70
        int u = i.first, v = i.second;
71
        if(du[u] >= 3 && du[v] >= 3){
72
            ans = 2;
73
            break;
74
        }
75
    }
76

77
    // 处理核心点
78
    for(int i = 1; i <= n; i++){
79
        if(du[i] >= 4) core[i] = 1;
80
    }
81

82
    for(int i = 1; i <= n; i++){
83
        if(core[i] && !st[i]){
84
            p.clear();
85
            max_dist = 0;
86
            far_node = i;
87
            dfs(i, -1, 0);
88
            for(auto& j : p) st[j] = 0;
89
            int u = far_node;
90
            max_dist = 0;
91
            //for(int j = 1; j <= n; j ++) st[j] = 0;
92
            dfs(u, -1, 0);
93
            int v = far_node;
94
            int add = 1;
95
            if(check(u)) add++;
96
            if(u != v && check(v)) add++;
97
            if(u == v){
98
                int t = 0;
99
                for(int i = h[u]; ~i; i = ne[i]){
100
                    if(du[e[i]] == 3){
101
                        t++;
102
                    }
103
                }
104
                if(t >= 2) add++;
105
            }
106
            ans = max(ans, max_dist + add);
107
        }
108
    }
109

110
    cout << ans << endl;
111
}
112

113
signed main(){
114
    IOS;
115
    int _ = 1;
116
    cin >> _;
117
    while(_--){
118
        solve();
119
    }
120
}

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
using PII = pair<int, int>;
5
#define int long long
6
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
7
const int N = 2e5 + 10, mod = 998244353;
8

9
int n, m, ans;
10
int du[N];// 无向图度
11
int h[N], e[N * 2], ne[N * 2], idx;
12
vector<int> p;
13

14
void init(){
15
    idx = 0;
16
    ans = 1;
17
    for(int i = 0; i <= n; i++) {
18
        h[i] = -1;
19
        du[i] = 0;
20
    }
21
}
22

23
void add(int a, int b){
24
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
25
}
26

27
int dfs(int u, int fa){
28
    vector<int> child;
29
    for(int i = h[u]; ~i; i = ne[i]){
30
        int v = e[i];
31
        if(v == fa) continue;
32
        int val = dfs(v, u);
33
        if(val > 0) child.push_back(val);
34
    }
35

36
    // 从大到小排序
37
    sort(child.rbegin(), child.rend());
38

39
    int dp_u = 0;
40
    if(du[u] >= 4){
41
        // 可以作为中间节点或者端点
42
        dp_u = 1; //自己作为端点
43
        if(!child.empty()){
44
            dp_u = max(dp_u, 1 + child[0]); //该节点
45
            ans = max(ans, 1 + child[0]);
46
        }
47
        // 作为中间节点
48
        if(child.size() >= 2){
49
            ans = max(ans, 1 + child[0] + child[1]);
50
        }
51
    }else if(du[u] == 3){
52
        // 只能作为端点
53
        dp_u = 1;
54
        if(!child.empty()){
55
            ans = max(ans, 1 + child[0]);
56
        }
57
        ans = max(ans, 1LL);
58
    }
59
    return dp_u;
60

61
}
62

63
void solve(){
64
    cin >> n;
65
    init();
66
    for(int i = 1; i < n; i++){
67
        int u, v;
68
        cin >> u >> v;
69
        add(u, v), add(v, u);
70
        du[u]++, du[v]++;
71
    }
72

73
    dfs(1, -1);
74
    cout << ans << endl;
75
}
76

77
signed main(){
78
    IOS;
79
    int _ = 1;
80
    cin >> _;
81
    while(_--){
82
        solve();
83
    }
84
}