C. Uncle Bogdan and Country Happiness

• Quiz
  • https://codeforces.com/problemset/problem/1388/C
• AC
  • https://codeforces.com/contest/1388/submission/97891528
• 感想
  • 分かったつもりでスキップしていたが、実際に解いてみるとハマって何時間もかかった
  • 結局editorialを見てAC
  • 確実に求められる値（今回で言えばA, g）を求めて、確実に成り立っていなければならない性質をチェックすればいい

code

editorialと同じ変数名にしています

void solve(){
  ll N,M;
  cin>>N>>M;
  
  VI P(N);
  rep(i,N)cin>>P[i];

  VI H(N);
  rep(i,N)cin>>H[i];
  
  VV G(N);
  rep(i,N-1){
    ll a,b;cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  VI A(N, -1);
  // i以下の部分木の帰宅者の和（何人が通過する？）
  function<ll(ll,ll)> dfs = [&](ll i, ll prev){
    if(A[i]!=-1)return A[i];
    ll sum = P[i];
    for(ll to : G[i]){
      if(to==prev)continue;
      sum += dfs(to, i);
    }
    return A[i]=sum;
  };
  dfs(0, -1);

  rep(i,N){
    // 通過者とハピの偶奇は一致する
    // if(A[i]%2 != H[i]%2){ // これだとH[i]が負のときダメ
    if((A[i]+H[i])%2==0){
      // ok
    }else{
      debug("parity error",i);
      p_no();return;
    }
  }

  // 各点をhappyで通過した「人数」
  VI g(N);
  rep(i,N){
    g[i] = (H[i]+A[i])/2;
  }

  rep(i,N){
    if(0<=g[i] && g[i]<=A[i]){
      // ok
    }else{
      debug("g is contradicted");
      p_no();return;
    }
  }

  // 子供チェック用dfs
  bool ok=true;
  function<void(ll,ll)> DFS = [&](ll i, ll prev){
    ll g_sum=0;
    for(ll to : G[i]){
      if(to==prev)continue;
      g_sum += g[to];
      DFS(to,i);
    }
    if(g_sum>g[i]){
      ok=false;
    }
  };
  DFS(0, -1);
  if(!ok){
    p_no();return;
  }
  p_yes();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}