結果

問題 No.1030 だんしんぐぱーりない
ユーザー TAISA_TAISA_
提出日時 2020-04-17 22:46:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,438 bytes
コンパイル時間 3,214 ms
コンパイル使用メモリ 226,924 KB
実行使用メモリ 34,432 KB
最終ジャッジ日時 2024-10-03 14:28:00
合計ジャッジ時間 11,782 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 3 ms
5,248 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 998244353LL;
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
template <class T>
void chmin(T &a, T b) { a = min(a, b); }
template <class T>
void chmax(T &a, T b) { a = max(a, b); }
void debug() { cerr << "ok" << endl; }
template <class T>
void vout(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
    }
} //Point Update Range Get
template <class T>
struct Segtree2 {
    inline T f(const T &a, const T &b) { return max(a, b); }
    inline void act(T &a, const T &b) { a = b; }
    int n;
    T e;
    vector<T> dat;
    Segtree2(int n_, T e) : e(e) {
        n = 1;
        while (n < n_) {
            n <<= 1;
        }
        dat.resize(2 * n, e);
    }
    void upd(int k, const T &x) {
        k += n;
        act(dat[k], x);
        k >>= 1;
        while (k > 0) {
            dat[k] = f(dat[k << 1], dat[k << 1 | 1]);
            k >>= 1;
        }
    }
    T get(const int &a, const int &b, int k, int l, int r) {
        if (b <= l || r <= a) {
            return e;
        }
        if (a <= l && r <= b) {
            return dat[k];
        }
        return f(get(a, b, k << 1, l, (l + r) >> 1),
                 get(a, b, k << 1 | 1, (l + r) >> 1, r));
    }
    inline T get(const int &a, const int &b) { //[a,b)
        if (a >= b) {
            return e;
        }
        return get(a, b, 1, 0, n);
    }
};
//Path Sum and Subtree Sum
struct HLD {
    int n;
    vector<vector<int>> G;
    vector<int> sz, rt, id, par, out;
    V<ll> c;
    int pos;
    Segtree2<ll> seg;
    HLD(int n, V<ll> &c) : seg(n, 0LL), c(c), n(n), G(n), sz(n, 1), rt(n, -1), id(n), par(n, -1), out(n) {}
    void addedge(int u, int v) {
        G[u].eb(v);
        G[v].eb(u);
    }
    void build() {
        szdfs(0, -1);
        id[0] = 0;
        rt[0] = 0;
        pos = 0;
        hld(0, -1);
        for (int i = 0; i < n; i++) {
            seg.upd(id[i], c[i]);
        }
    }
    void szdfs(int i, int p) {
        for (auto &e : G[i]) {
            if (e == p) continue;
            szdfs(e, i);
            par[e] = i;
            sz[i] += sz[e];
            if (sz[e] > sz[G[i][0]]) {
                swap(G[i][0], e);
            }
        }
    }
    void hld(int i, int p) {
        id[i] = pos;
        pos++;
        for (auto &e : G[i]) {
            if (e == p) continue;
            if (e == G[i][0]) {
                rt[e] = rt[i];
            } else {
                rt[e] = e;
            }
            hld(e, i);
        }
        out[i] = pos;
    }
    inline ll f(int a, int b) { return seg.get(a, b + 1); } //[a,b]
    ll get_v(int u, int v) {
        ll res = 0;
        while (1) {
            if (id[u] > id[v]) swap(u, v);
            if (rt[u] == rt[v]) {
                chmax(res, f(id[u], id[v]));
                break;
            } else {
                chmax(res, f(id[rt[v]], id[v]));
                v = par[rt[v]];
            }
        }
        return res;
    }
    ll subtree(int u) {
        return f(id[u], out[u]);
    }
};
vector<vector<int>> G;
struct LCA {
    int n;
    vector<vector<int>> par;
    vector<int> dep;
    void dfs(int i, int p) {
        par[0][i] = p;
        for (auto &e : G[i]) {
            if (e == p) continue;
            dep[e] = dep[i] + 1;
            dfs(e, i);
        }
    }
    void build(int n_) {
        n = n_;
        dep.resize(n);
        par.resize(30, vector<int>(n, -1));
        for (int i = 1; i < 30; i++) {
            for (int j = 0; j < n; j++) {
                if (par[i - 1][j] != -1) {
                    par[i][j] = par[i - 1][par[i - 1][j]];
                }
            }
        }
        dfs(0, -1);
    }
    int get(int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        for (int i = 19; i >= 0; i--) {
            if (((dep[v] - dep[u]) >> i) & 1) v = par[i][v];
        }
        if (u == v) return u;
        for (int i = 19; i >= 0; i--) {
            if (par[i][u] != par[i][v]) {
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }
};
//Point Update Range Get
template <class T>
struct Segtree {
    LCA g;
    T e;
    inline T f(const T &a, const T &b) {
        if (a == e) {
            return b;
        } else if (b == e) {
            return a;
        }
        return g.get(a, b);
    }
    inline void act(T &a, const T &b) { a = b; }
    int n;
    vector<T> dat;
    Segtree(int n_, T e) : e(e) {
        n = 1;
        while (n < n_) {
            n <<= 1;
        }
        dat.resize(2 * n, e);
    }
    void upd(int k, const T &x) {
        k += n;
        act(dat[k], x);
        k >>= 1;
        while (k > 0) {
            dat[k] = f(dat[k << 1], dat[k << 1 | 1]);
            k >>= 1;
        }
    }
    T get(const int &a, const int &b, int k, int l, int r) {
        if (b <= l || r <= a) {
            return e;
        }
        if (a <= l && r <= b) {
            return dat[k];
        }
        return f(get(a, b, k << 1, l, (l + r) >> 1),
                 get(a, b, k << 1 | 1, (l + r) >> 1, r));
    }
    inline T get(const int &a, const int &b) { //[a,b)
        if (a >= b) {
            return e;
        }
        return get(a, b, 1, 0, n);
    }
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k, q;
    cin >> n >> k >> q;
    G.resize(n);
    V<ll> c(n), a(k);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        --a[i];
    }
    HLD g(n, c);
    for (int i = 0; i + 1 < n; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        G[u].eb(v);
        G[v].eb(u);
        g.addedge(u, v);
    }
    g.build();
    Segtree<int> lca(k + 10, -1);
    lca.g.build(n);
    for (int i = 0; i < k; i++) {
        lca.upd(i, a[i]);
    }
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        --x;
        --y;
        if (t == 1) {
            lca.upd(x, y);
        } else {
            int l = lca.get(x, y + 1);
            //cout << l << '\n';
            cout << g.get_v(0, l) << '\n';
        }
    }
}
0