題目背景

墨家家主有棵樹。
題目描述

給定一個保存樹節(jié)點(diǎn)信息的數(shù)據(jù)結(jié)構(gòu)，它包含了樹節(jié)點(diǎn)唯一的 id ，樹節(jié)點(diǎn)值 和 直系子節(jié)點(diǎn)的 id 。

比如，樹節(jié)點(diǎn)1是樹節(jié)點(diǎn)2的父節(jié)點(diǎn)，樹節(jié)點(diǎn)2是樹節(jié)點(diǎn)3的父節(jié)點(diǎn)。他們相應(yīng)的樹節(jié)點(diǎn)值為 9 , 4 , 1 。那么樹節(jié)點(diǎn)1的數(shù)據(jù)結(jié)構(gòu)是 [1, 9, [2]] ，樹節(jié)點(diǎn)2的數(shù)據(jù)結(jié)構(gòu)是 [2, 4, [3]] ，樹節(jié)點(diǎn)3的數(shù)據(jù)結(jié)構(gòu)是 [3, 1, []] 。注意雖然樹節(jié)點(diǎn)3也是樹節(jié)點(diǎn)1的一個子節(jié)點(diǎn)，但是由于并不是直系子節(jié)點(diǎn)，因此沒有體現(xiàn)在樹節(jié)點(diǎn)1的數(shù)據(jù)結(jié)構(gòu)中。

現(xiàn)在輸入一棵樹的所有樹節(jié)點(diǎn)信息，以及單個樹節(jié)點(diǎn)id，返回這個樹節(jié)點(diǎn)和它所有子節(jié)點(diǎn)的節(jié)點(diǎn)值之和。
輸入格式

第一行輸入一個整數(shù)N，代表共有N個樹節(jié)點(diǎn)。

接下來輸入N個樹節(jié)點(diǎn)，每個樹節(jié)點(diǎn)第一行輸入它的id，第二行輸入節(jié)點(diǎn)的值，第三行輸入直系子節(jié)點(diǎn)的個數(shù)M，第四行輸入M個直系子節(jié)點(diǎn)的id值。

最后一行輸入一個樹節(jié)點(diǎn)id。
輸出格式

一個整數(shù)，最后一行輸入的樹節(jié)點(diǎn)的和它所有子節(jié)點(diǎn)的節(jié)點(diǎn)值之和。
輸入輸出樣例
輸入

3
1
5
2
2 3
2
3
0
3
3
0
1

輸出

11

說明/提示

樹節(jié)點(diǎn) 1 自身的節(jié)點(diǎn)值是 5 ，他有兩個直系子節(jié)點(diǎn) 2 和 3 ，而且 2 和 3 的節(jié)點(diǎn)值均為 3 。因此樹節(jié)點(diǎn) 1 的總節(jié)點(diǎn)值是 5 + 3 + 3 = 11 。

一個樹節(jié)點(diǎn)最多有一個直系父節(jié)點(diǎn)，但是可以有多個直系子節(jié)點(diǎn)。

節(jié)點(diǎn)數(shù)量不超過 2000 。

解題思路：
正常模擬一棵樹！！！但是用vector容器，在規(guī)模較大的時候，效率比數(shù)組慢很多，觀察下面的數(shù)據(jù)點(diǎn)可以知道，最后兩個數(shù)據(jù)點(diǎn)，用vector容器的寫法是過不了的。

代碼如下：

#include <iostream> #include <vector> using namespace std; const int N = 1010; vector<int>tnode[N]; int w[N]; int ans; void dfs(int node) {ans+=w[node];for (int i = 0;i<tnode[node].size();i++){dfs(tnode[node][i]);} }int main() {int cnt;cin>>cnt;while(cnt--){int id,chiln;cin>>id;cin>>w[id];cin>>chiln;if (chiln==0) continue;else{for (int i = 1;i<=chiln;i++){int chilid;cin>>chilid;tnode[id].push_back(chilid);}}}int root;cin>>root;dfs(root);cout<<ans<<endl;return 0; }

代碼如下：

#include <iostream> using namespace std; const int N = 2010; int ans;struct node {int w;int ch[N];int size; };node tnode [N];void dfs(int root) {ans += tnode[root].w;for (int i = 1; i <= tnode[root].size; i++) {dfs(tnode[root].ch[i]);} }int main() {int cnt;cin >> cnt;while (cnt--) {int id, n;cin >> id;cin >> tnode[id].w;cin >> n;if (n == 0)continue;else {for (int i = 1; i <= n; i++) {cin >> tnode[id].ch[i];}tnode[id].size = n;}}int root;cin >> root;dfs(root);cout << ans << endl;return 0; }

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的树的节点值之和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。