Clock Tree(18785, P5, c++)

Clock Tree

Clock Tree

문제

(GPT 번역)
Farmer John의 새 헛간은 특이한 구조다.
방은 총 N개(2≤N≤2500)이고 1부터 N까지 번호가 매겨져 있다.
복도는 N−1개이며, 어떤 방에서든 복도를 따라 다른 모든 방으로 이동할 수 있다.
각 방에는 1~12가 적힌 원형 시계가 하나씩 있고 시계에는 시침은 항상 정수 눈금만 가리킨다.
소 Bessie는 모든 시계가 12를 가리키도록 맞추고 싶다.

Bessie는 헛간을 돌아다니면서 어떤 방에 ‘들어갈 때마다’ 그 방의 시계를 한 칸 앞으로 민다.
예를 들어 5를 가리키던 시계는 6이 되고, 12를 가리키던 시계는 1이 된다.
같은 방에 여러 번 들어가면 들어갈 때마다 한 칸씩 앞으로 간다.
Bessie가 어느 방에서 출발해야 모든 시계를 12로 맞출 가능성이 있는지를 알아내라.

출발한 방의 시계는 처음에는 움직이지 않는다.
하지만 그 방에 다시 들어오면 그때는 다른 방과 마찬가지로 한 칸 앞으로 간다.
시계는 Bessie가 방에 들어갈 때만 움직이며, 저절로는 움직이지 않는다.
또한 복도에 들어갔으면 반드시 반대쪽 끝으로 나와야 하며, 중간에서 되돌아올 수 없다.

입력

첫 줄에 N.
둘째 줄에 N개의 정수(각각 1~12): 각 방의 초기 시계 값.
다음 N−1줄에 복도 정보 a,b (1~N): 방 a와 b가 연결되어 있음.

출력

Bessie가 출발했을 때 모든 시계를 12로 맞출 수 있는 출발 방의 개수를 출력한다.

풀이

우선 문제 조건으로 보면 복도는 N-1개이고 다른 모든 방으로 이동할 수 있으므로 트리 구조이다.

관찰을 하다보면 붙어있는 것들의 합이 시작지점 기준 1또는 0이 차이난다는 것을 확인할 수 있다.
(붙어있다는 의미는 간선으로 이어졌다는 뜻)

그래서 조금 더 관찰을 해보니 이분 그래프로 접근하면 깔끔하게 풀리는 것 같다.
모든 트리는 이분 그래프이기 때문에 임의의 시작 지점을 놓은 뒤 DFS를 통해 짝수 depth와 홀수 depth로 나눈다.
시작 방은 처음엔 증가하지 않고, Bessie가 이동할 때마다 도착한 방의 색 집합 합만 +1씩 늘어난다.

그러면 짝수 인덱스들의 합과 홀수 인덱스들의 합을 비교해서 답을 구할 수 있게 된다.
S_even이 짝수 인덱스 방의 수의 합, S_odd가 홀수 인덱스 방의 수의 합이라고 하면

S_even(mod 12) == S_odd(mod 12)라면 어디서 시작하든 가능하고
S_even(mod 12) == S_odd + 1(mod 12)라면 짝수 방에서 시작할 때 가능하고
S_even + 1 (mod 12) == S_odd(mod 12)라면 홀수 방에서 시작할 때 가능하다.
위의 경우가 전부 아니라면 불가능하다.

아이디어를 떠올리는게 어려웠던 문제다.

#define ll long long
#define i128 __int128_t
#include <bits/stdc++.h>
using namespace std;
long long n, m, t, k = 0;
bool flag = 0;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long mod = 998'244'353;
    using P=pair<int,int>;

    long long a, b, c, d;
    long long ans = 0;
    
    cin >> n;
    vector<int> v(n+1);
    for(int i=1;i<=n;i++)cin>>v[i];

    vector<vector<int>> graph(n+1);
    for(int i=0;i<n-1;i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int t_odd=0;
    int t_even=0;
    int cnt_odd=0;
    int cnt_even=0;
    vector<bool> visit(n+1, 0);

    function <void(int, bool)> dfs=[&](int x, bool ok){
        visit[x]=1;
        if(!ok){
            t_odd+=v[x];
            cnt_odd++;
        }
        else{
            t_even+=v[x];
            cnt_even++;
        }

        for(int i=0;i<graph[x].size();i++){
            if(!visit[graph[x][i]])
                dfs(graph[x][i], !ok);
        }
    };
    dfs(1, 0);

    t_odd%=12;
    t_even%=12;

    if(t_odd==t_even)cout<<n;
    else if((t_odd+1)%12==t_even)cout<<cnt_even;
    else if((t_even+1)%12==t_odd)cout<<cnt_odd;
    else cout<<0;

    return 0;
}