寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木

アルゴ式(beta版)の「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「さまざまなデータ構造 (#毎日アルゴ式)」8章:根付き木

僕が作成、提出したコードは、以下のとおりです。

Q1. 兄弟は誰だ? (1)

algo-method.com

/*
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)

algo-method.com

/*
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. 葉の個数

algo-method.com

/*
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. 行きがけ順

algo-method.com

/*
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. 帰りがけ順

algo-method.com

/*
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)

algo-method.com

/*
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)

algo-method.com

/*
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)

algo-method.com

/*
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