問題概要

$ N $頂点からなる木があり，$ i $番目の頂点には最初$ A_i $個の石が置かれている．

相異なる2つの葉を選び，その2頂点間のパス上にある頂点から石を1個ずつ取り除く．ただし，パス上の頂点で石が1個も置かれていない頂点がある場合，この操作はできない．

この操作を繰り返し，すべての頂点から石を取り除くことができるかどうかを求める．

解法概要

まず，木の各辺が何回使用されるべきかを$ A = \{ A_1, A_2, \cdots, A_n \} $から考える．

葉$ i $にくっついている辺なら$ A_i $回使用されるべき
葉にくっついていない辺については，ある頂点$ i $にくっついている辺の使用回数の合計は$ 2A_i $回であるべき

葉にくっついている辺はともかく，そうでない辺は他の辺の使用回数を見ないと使用されるべき回数を定めることができない．今回は木であるから，子が複数の親を持つことはないので，葉から根に向かって順番に辺の使用されるべき回数を特定していけばよい．これはdfsでできる．この使用回数が途中でおかしなことになったら，すべての頂点から石を取り除くことはできないということ．

次に「使用回数がおかしなことになる」というのはどういうことか考える．

まず，使用回数が途中で負になるのは明らかにおかしい．

また，使用回数が負にならなくてもすべての石を取り除くことができなくなる条件が存在する．

ここで，葉でない頂点$ i $にくっついている辺の集合$ E = \{ e_1, e_2, \cdots \} $について考える．頂点$ i $を含むパスが1度選ばれるたびに，頂点$ i $にくっついている辺のうち2つが使用されることになる．つまり，問題で指示されている操作は葉でない各ノードについて，集合$ E$の中の相異なる辺のペアを作る操作と言い換えられる．ここで，$ e_i $の使用されるべき回数を$ c_i $とすると，$ c_i > \frac{ \sum_j c_j }{ 2 } $である辺$ e_i $が存在する場合，その頂点からすべての石を取り除くことはできない．なぜならそのような場合，集合$ E$の中の辺の使用されるべき回数をすべて消費してペアを作るとき，辺$ e_i $同士のペアを作らざるを得ないためである．

よって，葉でない頂点にくっついている辺の使用回数チェックとしては

使用回数が負になっていないか？
$ c_i > \frac{ \sum_j c_j }{ 2 } $である辺$ e_i $はないか？

をチェックしなければならない．

ソースコード

#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

vector<int> used(100000);
vector<ll> stones(100000);
vector<int> tree[100000];

int root = 0;

/*
葉から根に向かってチェックしていくdfs
返り値は (nodeを呼び出したノード) -> (node) の辺が使用されるべき回数
途中でNOであることが判明したらその地点でLLONG_MAXを返す
*/
ll dfs(int node){
    used[node] = 1;

    int n = (int)tree[node].size();

    /* (根ではない)葉の場合 */
    if(node != root && n == 1) return stones[node];

    /* 葉でない (根も含む) 場合 */
    vector<ll> edges(n+1, 0);
    ll total = 0;
    rep(n){
        if(used[tree[node][i]]) continue;
        edges[i] = dfs(tree[node][i]);
        total += edges[i];
        if(edges[i] == LLONG_MAX) return LLONG_MAX;
    }
    /* (nodeを再帰で呼び出した頂点) -> (node) の辺が使用されるべき回数を求める */
    edges[n] = (stones[node]*2-total);
    if(edges[n] < 0) return LLONG_MAX;
    total += edges[n];
    for(ll edge: edges){
        if(edge > total/2) return LLONG_MAX;
    }
    return edges[n];
}

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    rep(n) cin >> stones[i];
    rep(n-1){
        int a,b;
        cin >> a >> b;
        a--; b--;
        tree[a].emplace_back(b);
        tree[b].emplace_back(a);
    }

    /*
    根の周りのエッジの使用回数チェックを省略するため，
    根は次数が1の頂点 (葉) になるようにする
    */
    while(tree[root].size() > 1) root++;

    ll ret = dfs(root);
    cout << (ret==LLONG_MAX?"NO":"YES") << endl;

    return 0;
}

感想

根を葉にすることと根の周りでの使用回数チェックをしていなかったためにin35，in36でのWAがなかなか取れなかった．
その上本記事では「くっついている辺」などという頭の悪そうな解説をしてしまった．
解いた問題の考え方をブログに書いておくと，ブログをぼんやり見返す無駄時間 (決して少なくない) が復習の時間と化して良いなあ．

NoiminのNoise

AtCoder Grand Contest 010 C - Cleaning

問題概要

解法概要

ソースコード

感想