dfs

#[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)

##前回の続き
[全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索](https://qiita.com/RubyLrving/items/449048d8a8ce9ae14d7c)

##深さ優先探索
###[D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d)

再起処理中に、O(N)をしたらTLEになります。
ということはデータ構造を学ぶ必要があります。

```C++:C++
#include <iostream>
#include <vector>
using namespace std;

vector<int> tree;
vector<int> a;
vector<int> b;

void dfs(int p, int x){
    
    tree[p] += x;
    
    for(int i=0; i<a.size(); i++){
        if(a[i] == p){
            dfs(b[i], x);
        }
    }
}

int main(void){
    int n, q;
    cin >> n >> q;
    
    tree.resize(n);
    
    a.resize(n-1);
    b.resize(n-1);
    for(int i=0; i<n-1; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    
    vector<int> p(q);
    vector<int> x(q);
    for(int i=0; i<q; i++){
        cin >> p[i] >> x[i];
        p[i]--;
    }
    
    for(int i=0; i<q; i++){
        dfs(p[i], x[i]);
    }
    
    for(int i=0; i<n; i++){
        cout << tree[i] << endl;
    }
}
```

###木構造を学ぶ
オブジェクトに子要素へのポインタを持たせます。
今回はこんな感じでもいけそう。

```C++:C++
class Node{
public:
    ll value_=0;
    vector<int> child_;
    Node(){}
};
```

問題の制約で最初の頂点が１と固定されています。
a, bの値を記録する際に、無方向グラフのイメージで親と子の両方にお互いを保持します。
dfsで親のIDと子のIDが同じ際には処理しないようにします。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class Node{
public:
    ll value_=0;
    vector<int> child_;
    Node(){}
};

vector<Node> tree;
 
void dfs(int p, int praent, ll x){
    tree[p].value_ += x;
    for(int i=0; i<tree[p].child_.size(); i++){
        if(tree[p].child_[i] != praent) dfs(tree[p].child_[i], p, tree[p].value_);
    }
}

int main(int argc, const char * argv[]) {
    int n, q;
    cin >> n >> q;
    tree.resize(n, Node());
    
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        tree[a].child_.push_back(b);
        tree[b].child_.push_back(a);
    }
    
    for(int i=0; i<q; i++){
        int p, x;
        cin >> p >> x;
        p--;
        tree[p].value_ += x;
    }
    
    dfs(0, 0, 0);
    
    for(int i=0; i<n; i++){
        if(i<n-1) cout << tree[i].value_ << ' ';
        else cout << tree[i].value_ << endl;
    }
}
```

###[Depth First Search](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja)
グラフは指向性グラフのイメージ。
最初の頂点は１と制約があるので１から計測。

一度も探索をされていなかったらdfsで探索を行います。
関数の最後で、一度も計測されていなかったら完了時刻を計測します。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class Node{
public:
    vector<int> child_;
    Node(){}
};

vector<Node> tree;

int d[100];
int f[100];
int t=1;
int n;

void dfs(int cnt){
    if(d[cnt] == 0){
        t++;
        d[cnt] = t;
    }
    vector<int> v;
    for(int i=0; i<tree[cnt].child_.size(); i++){
        int k = tree[cnt].child_[i];
        v.push_back(k);
    }

    for(int i=0; i<v.size(); i++){
        if(d[v[i]] == 0) dfs(v[i]);
    }
    
    if(f[cnt] == 0){
        t++;
        f[cnt] = t;
    }
}

int main(int argc, const char * argv[]) {

    cin >> n;
    tree.resize(n, Node());
    
    rep(i, n){
        int u, k;
        cin >> u >> k;
        u--;
        rep(j, k){
            int v;
            cin >> v;
            v--;
            tree[u].child_.push_back(v);
        }
    }
    d[0] = 1;

    for(int i=0; i<n; i++){
        if(d[i]<=1) dfs(i);
    }
    

    rep(i, n){
        cout << i+1 << ' ' << d[i] << ' ' << f[i] << endl;
    }

    return 0;
}
```