[boj 25977] k개 사과 트리 노드만으로 배를 최대로 수확하기

문제 링크

 

트리와 관련된 문제... 라고 할 수 있을까...

 

어떻게 풀어야할지 고민을 많이 했다.

 

n이 17보다 작거나 같다는 조건이 있었기에 그냥 브루트포스로 접근해도 되겠지 생각했지만, 어떻게든 최적화를 하고싶었다.

 

그리고 고민을 포기하고 그냥 브루트포스로 풀었다... ㅎㅎ;;

 

import sys
input = sys.stdin.readline


def solve():
    N, K = map(int, input().split())
    P = [0] * N
    
    for _ in range(N-1):
        u, v = map(int, input().split())
        P[v] = u
    
    state = list(map(int, input().split()))
    
    ans = 0
    for i in range(1<<N):
        temp = []
        for j in range(N):
            if i & (1<<j): temp.append(j)
            
        V = [0] * N
        for t in temp:
            V[t] = 1
        
        if not V[0]: continue
        
        is_available = True
        
        for t in temp:
            if not is_available: break
            
            while True:
                t = P[t]
                if t == 0: break
                
                if not V[t]:
                    is_available = False
                    break
        
        
        if is_available:
            tmp, cnt = 0, 0
            for t in temp:
                if state[t] == 1: cnt += 1
                elif state[t] == 2: tmp += 1
        
        if cnt <= K: ans = max(ans, tmp)
    
    print(ans)
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()