2023.1.18 PM 09:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=j124 出題者 : 2022年10月APCS 標籤 : 遞迴、stack 難易度 : 3
解題想法 : 此題亦可使用暴力遞迴,但筆者此題使用的是stack解法。 輸入是一個樹的前序遍歷,因此可以利用stack的特性來做讀取,方法是每讀取一個值,就將它推進child[stack.top()]中,且若遇到非0的數值就push進stack,蒐集完child以後就pop,要如何判斷是否蒐集完,可以利用取得child[stack.top()]的長度來判斷,若為偶數則長度為2就蒐集完,若為奇數則長度為3才收集完,判斷方式有很多種,筆者的方式可參考下面的code。 讀取完以後就很容易實作了,只要把每個節點(若child是0需跳過)分別和自己的child相減取絕對值並加總起來即可(節點可用另一個陣列存),但C/C++記得要開long long。
//C++ language
#include<iostream>
#include<stack> //stack
#include<vector> //vector
#include<unordered_set> //unordered_set
using namespace std;
int main(){
stack<int>stk;
vector<int> child[int(1e5+1)]={};
vector<int> v;
int n; cin>>n;
stk.push(n); v.push_back(n);
while(cin>>n){
child[stk.top()].push_back(n);
if(child[stk.top()].size() == 2+(stk.top()%2)) stk.pop();
if(n != 0) stk.push(n), v.push_back(n);
}
long long ans=0;
for(int i: v){
for(int j: child[i]){
if(j==0) continue;
ans+=abs(i-j);
}
}
cout<<ans<<"\n";
return 0;
}

## Python language
stk=[]
child=[[] for _ in range(100005)] #勿使用[]*100005
a=[]
def stk_top(): return stk[-1]
def stk_push(x): stk.append(x)
def stk_pop(): stk.pop()
nodes=[int(x) for x in input().split()]
stk_push(nodes[0]); a.append(nodes[0])
for n in nodes[1:]:
child[stk_top()].append(n)
if len(child[stk_top()]) == 2+(stk_top()%2): stk_pop()
if n!=0:
stk_push(n)
a.append(n)
ans=0
for i in a:
for j in child[i]:
if j==0: continue
ans+=abs(i-j)
print(ans)
