題目：點此
題目描述
在這個問題中，給定一個值S和一棵樹，在樹的每個節點有一個正整數，問有多少條路徑的節點總和達到S，路徑中節點的深度必須是升序的，假設節點1是根節點，根的深度是0，它的兒子節點的深度為1，路徑不必一定從根節點開始，
輸入格式
第一行是兩個整數N和S，其中N是樹的節點數， 第二行是N個正整數，第i個整數表示節點i的正整數， 接下來的N-1行每行是2個整數x和y，表示y是x的兒子，
輸出格式
輸出路徑節點總和為S的路徑數量，
思路
先準備資料結構：(描述思路時會用到，先給出定義和使用）
1.vector <int> tree[100000],鄰接表（把樹看成DAG圖）
2.int a[100000]={0},前綴和陣列
3.bool color[100001]={false},dfs時使用，true代表訪問過，false代表沒訪問過
4.int weight[100000],存盤權值（鄰接表不存權值）
5.set <int> r,找根節點（r內的為可能是根節點的元素）
先讀入n，s；再讀入權值，并將i存入鄰接表，權值存入weight，
接著讀入x、y，將y插在tree[i]的后面并從集合r中洗掉y（y有雙親結點（父節點），不可能是根）
最后r中剩下的就是根，存起來（我的root變數），前綴和陣列a[0]清零，接著進入dfs：（用遞回）
將color[當前訪問頂點編號（我的now變數）]置成true，表示已訪問，接著計算該節點的前綴和*，然后找結點繼續dfs，當結點訪問完畢后，用二分搜索找前綴和陣列中是否有a[現深度（deep）]-s(在dfs函式里設個變數名打成p了，不過沒有關系），若有路徑數量++，
*：見附錄1
犯的錯誤
1.二分查找找的是a[deep]-s而不是s，
2.應該用遞回實作dfs，而不是用堆疊，應為用遞回比較熟練，不容易錯，
3.樹根不一定是零，需要找樹根，
4.應該用weight陣列存權值而不是tree[XX][0]，
識訓
1.要注意前綴和：a[i]+a[i+1]+···+a[j]=(a[1]+a[2]+···+a[i-1])-(a[1]+a[2]+a[3]+a[4]+···+a[j])
2.在條件允許的情況下，要用自己熟練的方法解體，
3.不要想當然，不要有僥幸心理，
4.在n<=100000的情況下，不要怕多開幾個陣列，
附錄一
這里用的前綴和是一條從根節點出發的路徑上的前綴和
如上圖，它原來的路徑是12--11--7--6--3，現在變成了12--11--7--6--5，所以陣列變成了12、23、30、36、41，
現在路徑變成了12--11--7--8,陣列變成了12、23、30、38、41，
由于陣列是有序的，所以查找有沒有路經總和為S是要用二分查找優化，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56831.html
標籤：C++
下一篇：二值影像連通域標記演算法優化