ABC138 D - Ki (400) DFSとBFSで解く方法

問題リンク

atcoder.jp

方針

カウンターに足されるxのことを仮にcostと呼ぶことにして、最終的に頂点iに足されたcostの総和をcost[i]とすると、そのcost[i]は、根から近い方からiを見ていって、その親を足していけばよい。

根から近い方から見るので、DFSかBFSで実現できる。

提出コード

DFS

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(ll i=0;i<N;++i)
typedef long long int ll;

int N,Q;
vector<vector<ll> > G(200010);
vector<ll> cost(200010);
vector<bool> visited(200010,false);

void dfs(int v, int pv){
    visited[v] = true;
    if(v != 0)cost[v]+=cost[pv];
    for(auto nv: G[v]){
        if(visited[nv] == false) dfs(nv, v);
    }
}

int main(){
    cin >> N >> Q;
    
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    
    rep(i,Q){
        int a,b; cin >> a >> b;
        a--;
        cost[a] += b;
    }

    dfs(0,0);
    rep(i,N-1) cout << cost[i] << " ";
    cout << cost[N-1] << endl;
}

BFS

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(ll i=0;i<N;++i)
typedef long long int ll;
 
int N,Q;
vector<vector<ll> > G(200010);
vector<ll> cost(200010);
vector<bool> visited(200010,false);
 
void bfs(int s){
    queue<int> que; que.push(s);
    visited[s] = true;
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(auto nv: G[v]){
            if(visited[nv] == false){
                que.push(nv);
                cost[nv] += cost[v];
                visited[nv] = true;
            }
        }
    }
}
 
int main(){
    cin >> N >> Q;
    
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    
    rep(i,Q){
        int a,b; cin >> a >> b;
        a--;
        cost[a] += b;
    }
 
    bfs(0);
    rep(i,N-1) cout << cost[i] << " ";
    cout << cost[N-1] << endl;
}