ABC187 E - Through Path

けんちょんさんの記事見て解説ACしました。 drken1215.hatenablog.com

解説ACなのですが、身につくことがあったのでメモ記事を書きます。 競プロの問題といたよ履歴もこれで3つ目ですね。章構成のテンプレとか挿入できるようにしておきたい。

問題

atcoder.jp

（コンテスト中に）考えたこと

制約的に計算量を落とす仕組みが必要。 「木　クエリ」で検索するとセグメント木が出てくる。色々見ているうちに遅延評価セグ木がいいのでは？と思ったりしたけど、セグ木の勉強をちょっとやってギブアップ

解答

木構造のimos法みたいな感じでした。 この問題の発展型みたいな感じらしいです。 atcoder.jp

悩んだポイントとしては、aとbのどっちがとりあえずの根（ここではノード0）に近いか？の判定方法です。 これを知るためにDFSしてたら本末転倒なので…。 これは木構造を根付き木として扱って、出発側の親が行っちゃいけないとこか否か、で判断できるみたいです。確かに…。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)

void dfs_root(vector<vector<long long>>& Graph, vector<long long>&root, vector<bool>&seen, long long cur){
    for(auto it : Graph[cur]){
        if(!seen[it]){
            seen[it] = true;
            root[it] = cur;
            dfs_root(Graph, root, seen, it);
        }
    }
}


void dfs_add(vector<vector<long long>>& Graph, vector<long long>&root, vector<bool>&seen, vector<long long> &add,long long cur, long long s){

    // current の addを処理
    seen[cur] = true;
    root[cur] = add[cur] + s;

    for(auto it : Graph[cur]){
        if(!seen[it]){
            dfs_add(Graph, root, seen, add, it, s + add[cur]);
        }
    }
}

int main(){

    long long n;
    cin >> n;

    vector<long long> a(n),b(n);
    vector<vector<long long>> Graph(n);
    rep(i,n - 1){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        Graph[a[i]].push_back(b[i]);
        Graph[b[i]].push_back(a[i]);
    }

    long long q;
    cin >> q;

    vector<long long> root(n, -1);
    vector<bool>      seen(n, false);
    seen[0] = true;
    dfs_root(Graph, root, seen, 0);

    vector<long long> add(n,0);
    rep(i,q){
        long long t,e,x;
        cin >> t >> e >> x;

        long long A,B;
        A = a[e - 1];
        B = b[e - 1];

        if(t == 2)
            swap(A,B);

        if(root[A] == B){
            add[A] += x;
        } else {
            add[0] += x;
            add[B] -= x;
        }
    }

    rep(i,n) root[i] = 0;
    rep(i,n) seen[i] = false;

    seen[0] = true;
    dfs_add(Graph, root, seen , add, 0, 0);

    rep(i,n){
        cout << root[i] << endl;
    }

    return 0;
}

学んだこと

• 根付き木において、隣接するノードのどちらが親側に近いかは、ノードの親がそれぞれなにか？を判定すればいい。（親がもう片方のノードになっているやつは、より根から遠い）
• セグ木の勉強をすると良い。（この問題は関係ないけど）

感想

解説を見ると通せないわけでもない、といった気がしてくるので、E問題もちょくちょく解いてみてなれておくと、本番で解けてぐっとレートが上がったりするのでは？と思ったりした。