Codeforces Round #722 (Div. 2) C. Parsa's Humongous Tree 木DP

題意(省略)

こう考えた

辺の合計を最大化するためには、各頂点の値は$l$あるは$r$のどちらかの値に振るのがよく、中間的な値は取らない．
ただし、各頂点を$l, r$どちらに寄せるのが良いのかはわからない．

考え方としては

• 1つの頂点$a$ 以外のすべての頂点が決まっているとするなら、$a$を$l, r$のどちらに寄せるべきかは自明である.

このため、適当な頂点(例えば0)をとり、葉から根に対して、自分が$l$である時を$[0]$で、$r$であるときを$[1]$として、それぞれのとき、子が$[0]$あるいは$[1]$どっちの時に大きな値になるかを判定し、加算していけば良い．

実装

int solve(){
    int n;
    cin >> n;

    vector<ll> values0(n);
    vector<ll> values1(n);
    vector<ll> dp0(n);
    vector<ll> dp1(n);

    ll a,b;
    REP(i, n){
        cin >> a >> b;
        values0.at(i) = a;
        values1.at(i) = b;
    }

    vector<vector<int>> G(n);

    REP(i, n-1){
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    list<int> q;
    list<int> qdepth;
    q.emplace_back(0); qdepth.emplace_back(0);



    vector<int> res(n);
    vector<int> depth(n, -1);
    vector<int> parent(n, -1);

    int curnode, curdepth;
    while(q.size() > 0) {
        curnode = q.front();
        q.pop_front();
        curdepth = qdepth.front();
        qdepth.pop_front();

        if (curnode >= 0) {
            depth.at(curnode) = curdepth;
            q.emplace_front(-1 - curnode);
            qdepth.emplace_front(curdepth);
            for (auto nextNode: G.at(curnode)) {
                if (depth.at(nextNode) != -1) continue;
                parent[nextNode] = curnode;
                q.emplace_front(nextNode);
                qdepth.emplace_front(curdepth + 1);
            }
        } else {
            ll val0, val1, curval;
            curnode = (-curnode) - 1;
            for(auto child: G[curnode]){
                if(child == parent[curnode]) continue;
                curval = values0[curnode];
                val0 = abs(curval - values0[child]) + dp0[child];
                val1 = abs(curval - values1[child]) + dp1[child];
                dp0[curnode] += max(val0, val1);

                curval = values1[curnode];
                val0 = abs(curval - values0[child]) + dp0[child];
                val1 = abs(curval - values1[child]) + dp1[child];
                dp1[curnode] += max(val0, val1);
            }

        }
    }
    cout << max(dp0[0], dp1[0]) << "\n";
    return 0;
}

using namespace std;
int main() {
    FASTIOpre();
    int q;
    cin >> q;
    REP(qq, q) solve();
}