xor의 성질상 A xor A = 0
만일 모든 노드를 xor한 값이 0이면 아무 간선이나 잡아도 YES임.
만일 모든 노드를 xor한 값이 V (V≠0)이면 노드들의 xor 값이 V인 서브트리가 존재한다는 이야기임.
이때 k=2이면 자동으로 정답은 NO가 됨.
아무튼 그 서브트리를 찾은 뒤 원래 트리에서 잘라내어 버리고,
남은 트리에서 다시 노드들의 xor 값이 V인 서브트리를 찾음.
그런 서브트리가 존재하지 않으면 NO를, 존재하면 YES
여기서 틀린 게 있을까
풀이는 맞음... 구현 문제인듯?
하 한번 더 훑어봐야겠다 레이팅 떨어질거 생각하니 눈물나네
틀린게 있다기보다 완벽한 증명이 아닌거같은데 만약 모든 노드를 xor 한 값이 6인데 각 노드의 값은 2,4인 크기 2의 트리가 있으면 전체 트리를 자르는건 안되니까 틀리지 않음?
예시가 이상하긴 한데 그리디하게 V만 잘랐을 때 된다는 증명이 부족한거같음
무슨 말인진 모르겠는데 생각해보다가 '잘라내어 버리는' 서브트리가 너무 크면 이상해지는 문제를 생각 안했다는 걸 깨달았음. 아이디어 ㄳ
모든 노드를 xor한 값이 0일 때도 2 2 3 3 이렇게 배열되어있으면 k값에 상관없이 no인데 yes라고 생각하는 풀이아닌지
2 / 2 3 3 하면 YES임
A xor A = 0이기 때문에 A에 어떤 수를 넣어도 성립함
그러네 같은 패리티면 사라지고 아니면 둘이 같구나
그럼 모든 노드를 xor한 값으로만 분할이 가능하다는걸 증명하면 풀릴듯. 난 다른 값으로도 될거같긴한데
계속보니까 V로만 분할 가능한듯 신기하네
이집트 애들이 XOR ㅈㄴ 좋아하길래 대회 전에 미리 좀 찾아봤음
코드 셀프리뷰해 봤는데 1. 루트노드를 판단하는 알고리즘이 잘못되었음. 어이없게도 2. 모든 노드 xor 값이 0이 아닐 때 저렇게 하는 것보다 좀 더 명확한 방법이 필요할듯. 내 코드는 서브트리를 정말로 잘라내어 '버려서', 2-2-2-1-1인데 2-2-2를 잘라내어 버리면 NO로 판단하게 됨.