だんしんぐぱーりない [yukicoder 1030]

https://yukicoder.me/problems/no/1030

前提知識

• LCAを載せたセグメントツリー

解説

https://yukicoder.me/submissions/466488

今回の問題はかみ砕くことで解きやすくなる。
問題で与えられている有向グラフは、根付き木として解釈することができる。
問題に書いてある、「会場は、上記のすべてのビーバーにとって到達可能な町にする。」とあるが、
この到達可能な町は、対象となるビーバーのLCAをとり、そのLCAである頂点から根である頂点までがすべて対象となる。
よって、引っ越しクエリを無視すれば、区間のLCAが取れれば、そこから根までのC[i]の最大値が答えになる。
これをやるために、「C[i] := i番目の町の活気」を事前にDFSをして、
「C[i] := i番目から根までの町の活気の最大値」のように変換しておこう。

あと残ったのは、区間LCAであるが、セグメントツリーが使える。
セグメントツリーの更新式にLCAを使うことで、区間LCAが取れる。
こうしておくことで、引っ越しクエリにも対応することができる。

int N, K, Q;
int C[101010], A[101010];
vector<int> E[101010];
SegTree<int, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int pa = -1) {
    fore(to, E[cu]) if (to != pa) {
        chmax(C[to], C[cu]);
        dfs(to, cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> Q;
    rep(i, 0, N) cin >> C[i];
    rep(i, 0, K) cin >> A[i];

    hld.init(N);
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
        hld.add(a, b);
    }
    hld.build(0);

    dfs(0);

    rep(i, 0, K) st.update(i, A[i] - 1);

    rep(_, 0, Q) {
        int T; cin >> T;
        if (T == 1) {
            int X, Y; cin >> X >> Y;
            X--; Y--;
            st.update(X, Y);
        }
        else {
            int L, R; cin >> L >> R;
            L--;

            int ans = C[st.get(L, R)];
            printf("%d\n", ans);
        }
    }
}