### [ZeroJudge - j124. 石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)
來源: APCS 2022/10 #dfs #tree

這題在APCS歷屆第三題以來算較輕鬆的一題
題目雖然有提到可以用樹的結構來解題
但其實只要利用dfs來模擬就可以了

**思路:**
構築一個dfs函式
如果石窟編號為0則回到上個節點, 否則計算當前石窟編號與上個石窟編號的差並加總
如果石窟編號為奇數則往下延伸出3條分支, 否則2條

> **Note:**
> 第一個節點沒有上一個節點 所以不能將第一個節點的數值與其他數加總

類似題: [APCS 2018/10 DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637)

code:

#include <bits/stdc++.h>
using namespace std;

long long sum = 0;
void dfs(int last){
    int n;
    cin >> n;
    if (!n)
        return;

    if (last)
        sum += abs(n-last);
    
    if (n & 1){
        dfs(n);
        dfs(n);
        dfs(n);
    }
    
    else {
        dfs(n);
        dfs(n);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    dfs(0);
    cout << sum;
}