P1352 상사 없는 파티

트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다.

상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값

점화식:

• val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가)
• val[node][0] = Σ max(val[child][0], val[child][1]) (현재 노드를 선택하지 않으면 자식들은 자유)

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

int val[100010][2], weight[100010];
vector<int> adj[100010];

void solve(int cur, int parent) {
    val[cur][0] = 0;
    val[cur][1] = weight[cur];
    for (int nxt : adj[cur]) {
        if (nxt == parent) continue;
        solve(nxt, cur);
        val[cur][1] += val[nxt][0];
        val[cur][0] += max(val[nxt][0], val[nxt][1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, u, v;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> weight[i];
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    solve(1, 0);
    cout << max(val[1][0], val[1][1]) << endl;
    return 0;
}

P2014 [CTSC1997] 수강 신청

가상의 루트(0번)를 만들어 트리를 구성하고, 정해진 개수의 과목을 선택하여 최대 학점을 얻는 문제입니다.

핵심 아이디어: 루트는 반드시 선택해야 하므로 실제로는 m+1개의 노드를 선택하는 것과 동일합니다.

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

const int MAXN = 305;
int dp[MAXN][MAXN], subtreeSize[MAXN];
int head[MAXN], nxtEdge[MAXN], toNode[MAXN], edgeCnt;
int n, m;

void addEdge(int u, int v) {
    toNode[++edgeCnt] = v;
    nxtEdge[edgeCnt] = head[u];
    head[u] = edgeCnt;
}

void dfs(int u) {
    for (int e = head[u]; e; e = nxtEdge[e]) {
        int v = toNode[e];
        dfs(v);
        for (int i = m + 1; i > 1; i--) {
            for (int j = 1; j < i && j <= subtreeSize[v]; j++) {
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j]);
            }
        }
        subtreeSize[u] += subtreeSize[v];
    }
    subtreeSize[u]++;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int pre, score;
        cin >> pre >> score;
        dp[i][1] = score;
        addEdge(pre, i);
    }
    dfs(0);
    cout << dp[0][m+1] << endl;
    return 0;
}

P2607 [ZJOI2008] 기사

각 노드가 정확히 하나의 부모를 가리키는 기반 트리(pseudo tree)에서 최대 가중치 독립집합을 구하는 문제입니다.

접근 방법:

1. 역방향 간선으로 트리 구성 (싫어하는 사람 → 자신)
2. 각 연결 요소에서 단 하나의 사이클 존재
3. 사이클의 각 엣지를 끊어며 트리 DP 수행

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000010, INF = 1e9;

int n, power[MAXN];
int h[MAXN], nxt[MAXN], dest[MAXN], removed[MAXN], idx;
ll dpInclude[MAXN][2], dpExclude[MAXN][2];
bool visited[MAXN], inStack[MAXN];
ll answer;

void add(int a, int b) {
    dest[idx] = b;
    nxt[idx] = h[a];
    h[a] = idx++;
}

void treeDP(int u, int forcedExclude, ll memo[][2]) {
    memo[u][0] = 0;
    memo[u][1] = (u == forcedExclude) ? -INF : power[u];
    
    for (int i = h[u]; ~i; i = nxt[i]) {
        if (removed[i]) continue;
        int v = dest[i];
        treeDP(v, forcedExclude, memo);
        memo[u][0] += max(memo[v][0], memo[v][1]);
        if (u != forcedExclude) {
            memo[u][1] += memo[v][0];
        }
    }
}

void findCycle(int u, int fromEdge) {
    visited[u] = inStack[u] = true;
    for (int i = h[u]; ~i; i = nxt[i]) {
        int v = dest[i];
        if (!visited[v]) {
            findCycle(v, i);
        } else if (inStack[v]) {
            removed[i] = 1;
            treeDP(v, -1, dpInclude);
            treeDP(v, u, dpExclude);
            answer += max(dpInclude[v][0], dpExclude[v][1]);
        }
    }
    inStack[u] = false;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int w, hates;
        cin >> w >> hates;
        add(hates, i);
        power[i] = w;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) findCycle(i, -1);
    }
    cout << answer << endl;
    return 0;
}

P3177 [HAOI2015] 트리 색칠

트리에서 정확히 K개의 노드를 검은색으로 칠할 때, 모든 검은색-흰색 쌍 사이의 거리 합을 최대화하는 문제입니다.

핵심 전환: 노드 쌍의 거리 → 각 간선이 몇 개의 쌍에 기여하는지 계산

간선 (u,v)의 가중치 w일 때, v의 서브트리에 k개의 검은색이 있다면 기여도는:

k*(m-k) + (sz[v]-k)*(n-m-sz[v]+k) × w

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2005;

struct Edge {
    int to, w, nxt;
} e[MAXN * 2];
int head[MAXN], tot, n, m, subtree[MAXN];
ll best[MAXN][MAXN];

void addEdge(int u, int v, int w) {
    e[tot] = {v, w, head[u]};
    head[u] = tot++;
}

void dfs(int u, int parent) {
    subtree[u] = 1;
    best[u][0] = best[u][1] = 0;
    
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == parent) continue;
        dfs(v, u);
        
        int limit = min(m, subtree[u] + subtree[v]);
        for (int j = limit; j >= 0; j--) {
            ll maxVal = -1;
            for (int k = max(0, j - subtree[u]); k <= min(j, subtree[v]); k++) {
                if (best[u][j-k] < 0 || best[v][k] < 0) continue;
                ll cross = (ll)k * (m - k) + (ll)(subtree[v] - k) * (n - m - subtree[v] + k);
                ll val = best[u][j-k] + best[v][k] + cross * e[i].w;
                maxVal = max(maxVal, val);
            }
            best[u][j] = maxVal;
        }
        subtree[u] += subtree[v];
    }
}

int main() {
    memset(head, -1, sizeof head);
    memset(best, -1, sizeof best);
    
    cin >> n >> m;
    if (n - m < m) m = n - m;
    
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    
    dfs(1, 0);
    cout << best[1][m] << endl;
    return 0;
}

P3478 [POI2008] STA-Station

모든 노드까지의 거리 합이 최대가 되는 루트를 찾는 문제입니다.

재루팅 기법: 루트를 이동할 때 거리 합의 변화를 O(1)에 계산

루트가 u에서 v(자식)로 바뀌면: newSum = oldSum - sz[v] + (n - sz[v])

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2000005;

int n, depth[MAXN], subtree[MAXN];
ll distSum[MAXN];
int h[MAXN], to[MAXN], nxt[MAXN], idx;

void addEdge(int u, int v) {
    to[++idx] = v;
    nxt[idx] = h[u];
    h[u] = idx;
}

void calcSize(int u, int parent) {
    subtree[u] = 1;
    depth[u] = depth[parent] + 1;
    for (int i = h[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        calcSize(v, u);
        subtree[u] += subtree[v];
    }
}

void reroot(int u, int parent) {
    for (int i = h[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        distSum[v] = distSum[u] - subtree[v] + (n - subtree[v]);
        reroot(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    
    calcSize(1, 0);
    for (int i = 1; i <= n; i++) distSum[1] += depth[i];
    reroot(1, 0);
    
    ll maxDist = -1;
    int bestRoot = 1;
    for (int i = 1; i <= n; i++) {
        if (distSum[i] > maxDist) {
            maxDist = distSum[i];
            bestRoot = i;
        }
    }
    cout << bestRoot << endl;
    return 0;
}

P1879 [USACO06NOV] Corn Fields G

인접한 두 칸을 동시에 선택할 수 없는 그리드 배치 문제의 전형적인 비트마스크 DP입니다.

상태: ways[row][mask] - i번째 행까지 채웠고, i번째 행의 선택 상태가 mask인 경우의 수

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

const int MAXR = 13, MAXM = 1 << 12, MOD = 1e8;

int ways[MAXR][MAXM], rowMask[MAXR];
bool valid[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int x; cin >> x;
            rowMask[i] = (rowMask[i] << 1) | x;
        }
    }
    
    for (int mask = 0; mask < (1 << m); mask++) {
        valid[mask] = !(mask & (mask >> 1));
    }
    
    for (int mask = 0; mask < (1 << m); mask++) {
        if (valid[mask] && (mask & rowMask[1]) == mask) {
            ways[1][mask] = 1;
        }
    }
    
    for (int i = 2; i <= n; i++) {
        for (int cur = 0; cur < (1 << m); cur++) {
            if (!valid[cur] || (cur & rowMask[i]) != cur) continue;
            for (int pre = 0; pre < (1 << m); pre++) {
                if (!valid[pre] || (pre & rowMask[i-1]) != pre) continue;
                if (cur & pre) continue;
                ways[i][cur] = (ways[i][cur] + ways[i-1][pre]) % MOD;
            }
        }
    }
    
    int ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ans = (ans + ways[n][mask]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

P1896 [SCOI2005] 서로 공격하지 않는 킹

체스판에 K개의 킹을 배치하되, 서로 공격 범위에 들어가지 않도록 하는 경우의 수를 세는 문제입니다.

상태 압축: 각 행의 킹 배치를 비트로 표현, 인접 비트가 동시에 1이면 불가능

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

const int MAXN = 10, MAXS = 2000;

int state[MAXS], kingCnt[MAXS], stateNum;
long long dp[MAXN][MAXS][100];
int n, targetK;

void genStates(int pos, int mask, int cnt) {
    if (pos >= n) {
        state[++stateNum] = mask;
        kingCnt[stateNum] = cnt;
        return;
    }
    genStates(pos + 1, mask, cnt);
    genStates(pos + 2, mask | (1 << pos), cnt + 1);
}

bool compatible(int a, int b) {
    return !(state[a] & state[b]) && 
           !((state[a] << 1) & state[b]) && 
           !((state[a] >> 1) & state[b]);
}

int main() {
    cin >> n >> targetK;
    genStates(0, 0, 0);
    
    for (int i = 1; i <= stateNum; i++) {
        dp[1][i][kingCnt[i]] = 1;
    }
    
    for (int row = 2; row <= n; row++) {
        for (int cur = 1; cur <= stateNum; cur++) {
            for (int pre = 1; pre <= stateNum; pre++) {
                if (!compatible(cur, pre)) continue;
                for (int k = targetK; k >= kingCnt[cur]; k--) {
                    dp[row][cur][k] += dp[row-1][pre][k - kingCnt[cur]];
                }
            }
        }
    }
    
    long long ans = 0;
    for (int i = 1; i <= stateNum; i++) {
        ans += dp[n][i][targetK];
    }
    cout << ans << endl;
    return 0;
}

P3959 [NOIP2017] 보물

트리를 구성하는데 사용된 간선 가중치 × 깊이의 합을 최소화하는 문제입니다.

집합 DP: f[subset][height] = subset을 포함하고 높이가 height인 트리의 최소 비용

새로운 레이어를 추가할 때: 기존 트리에서 새로운 레이어로 연결하는 최소 간선 가중치 합 × 현재 깊이

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

const int MAXN = 12, MAXM = 1 << MAXN, INF = 0x3f3f3f3f;

int n, m, dist[MAXN][MAXN];
int minEdge[MAXN][MAXM];
int dp[MAXM][MAXN];

int main() {
    scanf("%d%d", &n, &m);
    
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a--, b--;
        dist[a][b] = dist[b][a] = min(dist[a][b], c);
    }
    
    memset(minEdge, 0x3f, sizeof minEdge);
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int j = 0; j < n; j++) {
                if (mask >> j & 1) {
                    minEdge[i][mask] = min(minEdge[i][mask], dist[i][j]);
                }
            }
        }
    }
    
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < n; i++) dp[1 << i][0] = 0;
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
            int remain = mask ^ sub;
            int addCost = 0;
            for (int i = 0; i < n; i++) {
                if (remain >> i & 1) {
                    addCost += minEdge[i][sub];
                    if (addCost >= INF) break;
                }
            }
            if (addCost >= INF) continue;
            for (int h = 1; h < n; h++) {
                dp[mask][h] = min(dp[mask][h], dp[remain][h-1] + addCost * h);
            }
        }
    }
    
    int ans = INF;
    for (int h = 0; h < n; h++) {
        ans = min(ans, dp[(1 << n) - 1][h]);
    }
    printf("%d\n", ans);
    return 0;
}

P8189 [USACO22FEB] 선물 재분배

순환 그래프(각 노드가 특정 범위의 노드로 선물을 전달)에서 질의에 따른 분할 가능한 경우의 수를 계산합니다.

핵심: 순환 분할(cycle cover)의 개수를 계산하고, 두 집합으로 분할하는 경우의 수를 구함

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 19, MAXM = 1 << 18;

int n, queries;
int reachable[MAXN];
ll pathCnt[MAXM][MAXN], cycleCnt[MAXM], partitionCnt[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        bool selfLoop = false;
        for (int j = 0; j < n; j++) {
            int x; cin >> x; x--;
            if (!selfLoop) reachable[i] |= (1 << x);
            if (x == i) selfLoop = true;
        }
    }
    
    for (int i = 0; i < n; i++) {
        pathCnt[1 << i][i] = 1;
    }
    
    for (int mask = 1; mask < (1 << n); mask++) {
        int start = __lg(mask & -mask);
        for (int end = start; end < n; end++) {
            if (!pathCnt[mask][end]) continue;
            for (int nxt = start + 1; nxt < n; nxt++) {
                if ((mask >> nxt & 1) || !(reachable[end] >> nxt & 1)) continue;
                pathCnt[mask | (1 << nxt)][nxt] += pathCnt[mask][end];
            }
        }
    }
    
    for (int mask = 1; mask < (1 << n); mask++) {
        int start = __lg(mask & -mask);
        for (int end = 0; end < n; end++) {
            if (reachable[end] >> start & 1) {
                cycleCnt[mask] += pathCnt[mask][end];
            }
        }
    }
    
    partitionCnt[0] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        int first = mask & -mask;
        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if (!(sub & first)) continue;
            partitionCnt[mask] += cycleCnt[sub] * partitionCnt[mask ^ sub];
        }
    }
    
    cin >> queries;
    while (queries--) {
        string s; cin >> s;
        int setH = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'H') setH |= (1 << i);
        }
        int setG = ((1 << n) - 1) ^ setH;
        cout << partitionCnt[setH] * partitionCnt[setG] << "\n";
    }
    return 0;
}