트리 DP

4

나무의 중심

POJ 1655

4

트리의 최장 경로 최원점 쌍

POJ 1985

4

나무의 최대 독립 집합

POJ 2342

나무의 중심

n개의 결점이 없는 뿌리 없는 나무에 대해 점을 찾아 나무를 이 점을 뿌리로 하는 뿌리 있는 나무로 만들 때 최대 자수의 결점수가 가장 작고 이 점이 중심이다.다시 말하면 이 점을 삭제한 후 가장 큰 덩어리(틀림없이 나무)의 결점수가 가장 작다는 것이다.

POJ 1655

전형적인 나무의 중심을 구하는 제목으로 dfs로 수조 dp[i]로 i의 최대 자수 크기를 기록하고son[i]로 아들의 개수 나무를 기록하는 중심은 모든 노드 중 최대 자수 크기가 가장 작은 노드이다.

#include 
#include 
#include 
#include 
#define L 20010
using namespace std;

struct node{
    int nxt, to;
} a[L << 1];
int n, T, u, v, head[L], cnt, son[L], siz, ans, dp[L];

inline void add(int x, int y) {
    a[++cnt].nxt = head[x];
    a[cnt].to = y;
    head[x] = cnt;
}

inline void dfs(int s, int fa) {
    dp[s] = 0, son[s] = 1;
    for (int i = head[s]; i; i = a[i].nxt) {
        int u = a[i].to;
        if (u == fa) continue;
        dfs(u, s);
        dp[s] = max(dp[s], son[u]);
        son[s] += son[u];
    }
    dp[s] = max(dp[s], n - son[s]);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(head, 0, sizeof(head));
        memset(dp, 0, sizeof(dp));
        memset(son, 0, sizeof(son));
        cnt = 0;
        scanf("%d", &n);
        for (int i = 1; i < n; ++i) {
            scanf("%d %d", &u, &v);
            add(u, v), add(v, u);
        }
        dfs(1, 0);
        ans = 1, siz = dp[1];
        for (int i = 2; i <= n; ++i) 
            if (dp[i] < siz)
                ans = i, siz = dp[i];
        printf("%d %d
", ans, siz);
    }
    return 0;
}

트리의 최장 경로(최원점 쌍)

POJ 1985

트리 DP의 판자 문제는 끊임없이 dfs에서 각 점을 뿌리 노드의 가장 멀고 먼 길이로 업데이트하고 출력 길이와 최대 값을 출력하면 됩니다

#include 
#include 
#include 
#include 
#define L 1000010
using namespace std;

struct node{
    int nxt, to;
    long long l;
} e[L];
int n, m, a, b, head[L], cnt;
long long c, dp1[L], dp2[L], ans;
char pd[3];

inline void add(int a, int b, long long d) {
    e[++cnt].nxt = head[a];
    e[cnt].to = b;
    e[cnt].l = d;
    head[a] = cnt;
}

inline void dfs(int x, int fa) {
    for (int i = head[x]; i; i = e[i].nxt) {
        int u = e[i].to;
        if (u == fa) continue;
        dfs(u, x);
        if (dp1[x] < dp1[u] + e[i].l) dp2[x] = dp1[x], dp1[x] = dp1[u] + e[i].l;
        else dp2[x] = max(dp2[x], dp1[u] + e[i].l);
    }
    ans = max(ans, dp1[x] + dp2[x]);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %lld %s", &a, &b, &c, pd);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, 0);
    printf("%lld
", ans);
    return 0;
}

나무의 최대 독립 집합

POJ 2342

각 노드마다 두 가지 상황이 있는데 가든지 말든지 2차원 상태로 i가 가면 i의 아들이 갈 수 없다는 것을 나타낼 수 있다. dfs는 값을 업데이트하면 된다.

#include 
#include 
#include 
#include 
#define L 6000 + 10
using namespace std;

int n, a, b, root, fa[L], vis[L], dp[L][2];

inline void dfs(int x) {
    vis[x] = 1;
    for (int i = 1; i <= n; ++i) 
        if (fa[i] == x && !vis[i]) {
            dfs(i);
            dp[x][1] += dp[i][0];
            dp[x][0] += max(dp[i][1], dp[i][0]);
        }
}

int main() {
    while (scanf("%d", &n) == 1){
        for (int i = 1; i <= n; ++i) scanf("%d", &dp[i][1]);
        root = 0;
        while(scanf("%d %d", &a, &b) && a && b) fa[a] = b, root = b;
        memset(vis, 0, sizeof(vis));
        dfs(root);
        printf("%d
", max(dp[root][1], dp[root][0]));
    }
    return 0;
}