树形dp方法简述 - 帖子

因为没有环，所以该烃可以视为一棵树

简单提醒一下，就是把每一个点能连的H原子数统计出来，用树形dp统计最长链

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010, M = 400010; // 每个 C 最多产生4个键

int w[N];

int nxt[M], ver[M], head[N];
int tot;

int cnt[N], res; // cnt[i]表示从i到叶子节点的最长链
bool v[N];

void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

void dp(int x) {
    cnt[x] = w[x];
    v[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int &y = ver[i];
        if (v[y]) continue;
        dp(y);
        res = max(res, cnt[x] + cnt[y]); // 在更新cnt之前，更新res，否则可能会加两条同样的链
        cnt[x] = max(cnt[x], w[x] + cnt[y]); // 更新cnt
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) w[i] = 4; // 初始化，每个C能连4个
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
        --w[a], --w[b]; // C-C 两个 C 都少连一个 H
    }
    dp(1);
    printf("%d\n", res);
    return 0;
}