[BOJ 15107] Rainbow Roads

걍 좀 재밌게 푼 것 같아..
그림은 대충 그림판으로 휘적휘적, 문제요약 x

대충 이렇게 u-v-w로 연속된 정점들에 대해 u-v랑 v-w를 잇는 간선 색이 같으면, v를 루트로 볼 때 u의 서브트리와 w의 서브트리 내의 정점들은 답이 될 수 없다.
 
이제 저기서 v를 루트로 대충 dfs를 한다고 생각해보자. 진행중에 새로운 세 정점 x, y, z가 연결되어 있고, x-y와 y-z의 색이 같은 것은 다음과 같은 2가지 경우가 있다

초록색처럼 이제 x-y-z들이 부모로부터 내려오는 간선을 포함하는게 아니면, 어차피 부모로 영향을 못줘서 무시해도 된다.
파란색처럼 x-y-z들이 부모로 거슬러 올라갈 수 있으면, 그냥 모든 정점들이 답이 될 수 없다.
 
그래서 적당히 방문처리하면서 dfs슥슥하면 풀린다.
코드:
http://boj.kr/0fcda55946ec468bb31424ed1633ae37
 
근데 방문처리 안해도 돌길래 데이터 추가 요청 했어요 b