문제 1: 대회 참가 조합

각 참가자의 대회 참가 여부를 비트마스크로 인코딩하여 [0, 16) 범위의 정수로 표현한다. 이후 각 상태의 비트 개수(popcount)를 기준으로 내림차순 정렬한 뒤, 그리디 전략으로 조합을 구성한다.

핵심 아이디어는 sum[j]가 양수일 때, 현재 상태 j와 겹치지 않는 참가자를 병합하여 새로운 상태를 형성하는 것이다. 초기값을 충분히 큰 값으로 설정하여 가능한 모든 조합을 탐색할 수 있도록 한다.

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

typedef long long ll;
const int MAXN = 114514;
const ll INF = 1145141919810LL;

int n, m, fullMask;
ll participant[MAXN];
ll dp[1 << 4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    fullMask = (1 << m) - 1;
    
    for (int i = 1; i <= m; ++i) {
        int k, x;
        cin >> k;
        while (k--) {
            cin >> x;
            participant[x] |= (1 << (i - 1));
        }
    }
    
    sort(participant + 1, participant + n + 1);
    
    dp[0] = INF;
    for (int i = n; i >= 1; --i) {
        for (int mask = fullMask; mask >= 0; --mask) {
            if (dp[mask] > 0 && !(mask & participant[i])) {
                --dp[mask];
                ++dp[mask | participant[i]];
                break;
            }
        }
    }
    
    ll result = 0;
    for (int mask = 1; mask <= fullMask; ++mask) {
        result += dp[mask];
    }
    cout << result;
    
    return 0;
}

문제 2: 트리에서의 최대 가중치 연결 부분그래프

루트를 변경해가며 동적 계획법을 적용하는 문제. 각 정점을 루트로 하는 서브트리에서, 모든 정점의 차수가 k 이하이면서 루트의 차수는 k 미만인 연결 부분그래프의 최대 가중치를 계산한다.

두 단계로 해결:

1. 전처리 DFS: 각 정점을 기준으로 자식 방향으로만 확장했을 때의 최적값 down[v] 계산
2. 재루트 DFS: 부모에서 전달받은 값을 포함하여 현재 정점을 루트로 할 때의 전체 최적값 갱신

주의: k = 0인 경우를 반드시 예외 처리해야 한다. 미처리 시 모든 서브태스크에서 0점 처리될 수 있다.

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

typedef long long ll;
const int MAXV = 2290280;

struct Edge {
    int to, nxt, w;
} e[MAXV];

int head[MAXV], ecnt;
ll sub[MAXV];
int n, limit;
ll bestAns;

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

void calcDown(int u, int p) {
    vector<ll> cand;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == p) continue;
        calcDown(v, u);
        cand.push_back(sub[v] + e[i].w);
    }
    sort(cand.begin(), cand.end(), greater<ll>());
    int take = min(limit - 1, (int)cand.size());
    for (int i = 0; i < take; ++i) {
        sub[u] += cand[i];
    }
}

void reroot(int u, int p, ll fromParent) {
    vector<ll> all;
    all.push_back(fromParent);
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == p) continue;
        all.push_back(sub[v] + e[i].w);
    }
    sort(all.begin(), all.end(), greater<ll>());
    
    ll total = 0;
    for (auto v : all) total += v;
    bestAns = max(bestAns, total);
    
    ll prefix = 0;
    int use = min(limit - 1, (int)all.size());
    for (int i = 0; i < use; ++i) prefix += all[i];
    
    ll boundary = (all.size() >= limit) ? all[limit - 1] : 0;
    
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to, w = e[i].w;
        if (v == p) continue;
        ll childVal = sub[v] + w;
        ll upward = (childVal > boundary) ? prefix - childVal + boundary : prefix;
        reroot(v, u, upward + w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> limit;
    if (limit == 0) {
        cout << 0;
        return 0;
    }
    
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    
    calcDown(1, 0);
    reroot(1, 0, 0);
    cout << bestAns;
    
    return 0;
}

문제 3, 4

미해결. 난이도 판단 하에서 풀이 검토 후 추가 예정.