[NOIP 시뮬레이션] 케이블 트리 DP 분리

Description

   는 나무 한 그루를 주었는데 지금은 가장자리를 없애고 나무에 K개의 점이 존재하게 하고 각 점은 적어도 그 중의 한 점과 연결되어 최소 **변을 구한다.

Input

그룹 데이터, n개의 점의 트리, K 및 연결된 모서리.

Output

정답.

Sample input

2 4 4 1 2 3 4 3 1 1 1

Sample output

2 2

Solution :

Google은 DP[i][0∼1]를 지정하여 이 노드가 아버지 노드와 연결될 때의 최대 독립 변집을 나타냅니다. 그러면 우리는 이동 방정식을 얻을 수 있습니다.
DP[i][0]=∑DP[j][0]+max(max(DP[j][1]−DP[j][0]),0)
DP[i][1]=∑DP[j][0]
그러면 이 나무의 최대 독립 변집은
DP[1][0],
K가 최대 사이드 세트 * 2보다 크면 우리는 더 많은 연결을 필요로 한다
K-DP[1][0] ∗2의 모서리, 작으면 연결해야 합니다.
K/2+(Kand1) 모서리.

Code :

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

inline int read() {
    int i = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1; ch = getchar();
    }
    while(isdigit(ch)) {
        i = (i << 3) + (i << 1) + ch - '0'; ch = getchar();
    }
    return i * f;
}

const int MAXN = 1e5 + 5;
int dp[MAXN][2], first[MAXN], nxt[MAXN * 2], to[MAXN * 2], n, k, tot;

inline void addedge(int x, int y) {
    nxt[++tot] = first[x]; first[x] = tot; to[tot] = y;
    nxt[++tot] = first[y]; first[y] = tot; to[tot] = x;
}

inline void dfs(int x, int fa) {
    dp[x][1] = 1; dp[x][0] = 0;
    int mx = 0;
    for(int i = first[x]; i; i = nxt[i]) {
        if(to[i] != fa) {
            dfs(to[i], x);
            dp[x][1] += dp[to[i]][0];
            dp[x][0] += dp[to[i]][0];
            mx = max(dp[to[i]][1] - dp[to[i]][0], mx);
        }
    }
    dp[x][0] += mx;
}

int main() {
    int t = read();
    while(t--) {
        memset(first, 0, sizeof(first));
        memset(nxt, 0, sizeof(nxt));
        tot = 0;
        n = read(), k = read();
        for(int i = 1; i <= n - 1; ++i) addedge(read(), i + 1);
        dfs(1, 1); 
        int now = dp[1][0];
        if(now * 2 >= k) printf("%d
", k / 2 + (k & 1));
        else printf("%d
", now + k - now * 2); 
    }
}