[일반] ABC E번 어케 접근해야 함??

[펜져(penzer27)]

나는 애초에 문제 잘 못 이해하고 삽질한거 같은데 푼 사람 있음??

[익명(119.202)]

인접한 색이 다른거에 연결된 간선의 갯수가 a개라고 하면 간선이 홀수개 연결된 정점을 선택할때마다 a의 값이 홀수 <-> 짝수개로 바뀌는걸 이용하면 됨

[펜져(penzer27)]

예를 들어 엣지 3개인 노드를 봤을 때 연결 된 3개가 모두 선택안되어 있으면 3개가 추가 되지만, 3개 중에 이미 1개 선택 해 놓은 상황이면 2개 추가 되는거 아님??

[펜져(penzer27)]

아 이미 연결되어 있는 1개가 감소하면서 1개 삭제 2개 추가 되서 바뀌는구나.. ㄷㄷ ㄳ

[펜져(penzer27)]

그럼 홀수개마다 2 곱해주면 되겠네 ㄷㄷ

[익명(119.202)]

양방향으로 선택된 간선은 두 노드에서 둘 다 빠진다는걸 생각해야함. 원래 결과에서도 -1이 더 되어야해서 실제로는 그거보다 하나 더 빠질거임

[대학원오지마세요(publfl)]

빨간색으로 색칠한 애들의 모든 degree의 합을 생각해보면, u,v가 전부 빨간색일때 u-v란 edge는 총 2번씩 count되니까, 빨간색으로 색칠된 애들의 모든 degree의 합 = 빨간색-파란색 edge의 개수 + 빨간색-빨간색 edge의 개수x2가 되서 빨간색-파란색 edge의 개수와 mod 2로 같음

[펜져(penzer27)]

"mod 2로 같음" ㄷㄷ 멋있다. 답변 ㄳㄳ