アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木
僕が作成、提出したコードは、以下のとおりです。
Q1. 兄弟は誰だ？ (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q1. 兄弟は誰だ？ (1) https://algo-method.com/tasks/894 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> p(n,0); for(ll i=1;i<n;i++){ cin>>p[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[p[i]].push_back(i); } ll q; cin>>q; for(ll i=0;i<q;i++){ ll v; cin>>v; for(ll j=0;j<vv[p[v]].size();j++){ cout<<vv[p[v]][j]<<" "; } cout<<endl; } return 0; }
Q2. 兄弟は誰だ？ (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q2. 兄弟は誰だ？ (2) https://algo-method.com/tasks/895 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> p(n,0); vector<vector<ll>> vv(n); for(ll i=0;i<n-1;i++){ ll a,b; cin>>a>>b; p[b]=a; vv[a].push_back(b); } for(ll i=0;i<n;i++){ sort(vv[i].begin(),vv[i].end()); } ll q; cin>>q; for(ll i=0;i<q;i++){ ll v; cin>>v; for(ll j=0;j<vv[p[v]].size();j++){ cout<<vv[p[v]][j]<<" "; } cout<<endl; } return 0; }
Q3. 葉の個数
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q3. 葉の個数 https://algo-method.com/tasks/904 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> p(n); p[0]=0; for(ll i=1;i<n;i++){ cin>>p[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[p[i]].push_back(i); } ll ans=0; for(ll i=1;i<n;i++){ if(vv[i].size()==0){ ans++; } } cout<<ans<<endl; return 0; }
Q4. 行きがけ順
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q4. 行きがけ順 https://algo-method.com/tasks/905 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; vector<ll> num; void f(ll v,vector<vector<ll>> &vv){ num.push_back(v); for(auto i : vv[v]){ f(i,vv); } } int main(void){ ll n; cin>>n; vector<ll> a(n); a[0]=0; for(ll i=1;i<n;i++){ cin>>a[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[a[i]].push_back(i); } f(0,vv); assert(num.size()==n); for(ll i=0;i<n;i++){ cout<<num[i]<<((i==n-1) ? "\n" : " "); } return 0; }
Q5. 帰りがけ順
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q5. 帰りがけ順 https://algo-method.com/tasks/906 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; vector<ll> num; void f(ll v,vector<vector<ll>> &vv){ for(auto i : vv[v]){ f(i,vv); } num.push_back(v); } int main(void){ ll n; cin>>n; vector<ll> a(n); a[0]=0; for(ll i=1;i<n;i++){ cin>>a[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[a[i]].push_back(i); } f(0,vv); assert(num.size()==n); for(ll i=0;i<n;i++){ cout<<num[i]<<((i==n-1) ? "\n" : " "); } return 0; }
Q6. 箱の内部の箱の個数 (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q6. 箱の内部の箱の個数 (1) https://algo-method.com/tasks/909 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll f(ll v,vector<vector<ll>> &vv){ ll ret=vv[v].size(); for(auto i : vv[v]){ ret+=f(i,vv); } return ret; } int main(void){ ll n; cin>>n; vector<ll> a(n); a[0]=0; for(ll i=1;i<n;i++){ cin>>a[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[a[i]].push_back(i); } ll v; cin>>v; cout<<f(v,vv)<<endl; return 0; }
Q7. 箱の内部の箱の個数 (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q7. 箱の内部の箱の個数 (2) https://algo-method.com/tasks/907 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll f(ll v,vector<vector<ll>> &vv,vector<ll> &cnt){ if(cnt[v]!=-1){ return cnt[v]; } ll ret=vv[v].size(); for(auto i : vv[v]){ ret+=f(i,vv,cnt); } cnt[v]=ret; return ret; } int main(void){ ll n; cin>>n; vector<ll> a(n); a[0]=0; for(ll i=1;i<n;i++){ cin>>a[i]; } vector<vector<ll>> vv(n); for(ll i=1;i<n;i++){ vv[a[i]].push_back(i); } vector<ll> cnt(n,-1); f(0,vv,cnt); ll q; cin>>q; for(ll i=0;i<q;i++){ ll v; cin>>v; cout<<cnt[v]<<endl; } return 0; }
Q8. 兄弟は誰だ？ (3)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木 Q8. 兄弟は誰だ？ (3) https://algo-method.com/tasks/908 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void f(ll v,ll p,vector<vector<ll>> &vv,vector<vector<ll>> &vvl,vector<ll> &vl){ for(auto i : vv[v]){ if(i!=p){ vvl[v].push_back(i); vl[i]=v; f(i,v,vv,vvl,vl); } } } int main(void){ ll n; cin>>n; vector<vector<ll>> vv(n); for(ll i=0;i<n-1;i++){ ll a,b; cin>>a>>b; vv[a].push_back(b); vv[b].push_back(a); } vector<vector<ll>> vvl(n); vector<ll> vl(n,0); f(0,0,vv,vvl,vl); for(ll i=0;i<n;i++){ sort(vvl[i].begin(),vvl[i].end()); } ll q; cin>>q; for(ll i=0;i<q;i++){ ll v; cin>>v; for(ll j=0;j<vvl[vl[v]].size();j++){ cout<<vvl[vl[v]][j]<<(j==vvl[vl[v]].size()-1 ? "\n" : " "); } } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
