AtCoder Beginner Contest 138の振り返り - 宇宙船サンドボックス

はじめに

AtCoder Beginner Contest 138に参加したのでその振り返り。 A,B,C,D解けて、Eは初級レベルの失敗でTLEに、、悔やまれる。

A - Red or Not と B - Resistors in Parallel

Aはそのまま、Bはdoubleとか気をつけて実装する。

C - Alchemist

1回合成するたびに2で割ることになるので、小さいものから貪欲に合成していく。

D - Ki

入力段階では、単に頂点に値を足していって、最後にDFSで根からスタートして回答を一気につくる。

typedef long long ll;

vector<int> g[200005];
ll val[200005];

void dfs(int p, int c, ll sum){
  val[c] += sum;
  for(auto v : g[c]){
    if(v!=p){
      dfs(c, v, val[c]);
    }
  }
}

int main(int argc, char *argv[]) {
  int n,q;
  cin>>n>>q;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for(int i=0;i<q;i++){
    int p,x;cin>>p>>x;
    p--;
    val[p] += x;
  }
  dfs(-1, 0, 0);

  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<val[i];
  }
  cout<<endl;

  return 0;
}