結果

問題 No.1030 だんしんぐぱーりない
ユーザー Jumbo_kpr
提出日時 2020-04-18 04:57:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,965 ms / 2,000 ms
コード長 8,492 bytes
コンパイル時間 3,198 ms
コンパイル使用メモリ 154,292 KB
実行使用メモリ 29,696 KB
最終ジャッジ日時 2024-11-14 22:24:02
合計ジャッジ時間 44,401 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;
void yes(bool c) { if (c)print("Yes"); else print("No"); };
//const int mod = 1000000007;
const int mod = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x%mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
template<typename T>
struct edge {
    int src, to;
    T cost;
    edge(int to) :src(-1), to(to), cost(1) {}
    edge(int to, T cost) :src(-1), to(to), cost(cost) {}
    edge(int src, int to, T cost) :src(src), to(to), cost(cost) {}
    edge &operator=(const int &x) {
        to = x;
        return *this;
    }
    operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using Graph = vector<Edges<T>>;
template<typename T>
struct HeavyLightDecomposition {
    Graph<T> G;
    //next: child which makes heavy edge
    //head: head of heavy edge
    vector<int>sz, par, next, head, depth, index;
    int N;
    HeavyLightDecomposition(Graph<T> &g) :G(g) {
        N = G.size();
        sz.assign(N, 0);
        par.assign(N, 0);
        next.assign(N, -1);
        head.assign(N, 0);
        depth.assign(N, 0);
        index.assign(N, 0);
        build();
    }
    int dfs(int n) {
        int siz = 1, mx = 0;
        for (auto e : G[n]) {
            int nxt = e.to;
            if (nxt == par[n])continue;
            par[nxt] = n;
            siz += dfs(nxt);
            if (sz[nxt] > mx) {
                mx = sz[nxt];
                next[n] = nxt; //heavy edge
            }
        }
        return sz[n] = siz;
    }
    void assign_number() {
        queue<pair<int, int>>que; // push the head of heavy edge
        que.push({ 0,0 });
        int idx = 0;
        while (!que.empty()) {
            int n = que.front().first;
            int d = que.front().second;
            que.pop();
            index[n] = idx++;
            depth[n] = d;
            int h = n;
            head[n] = n;
            while (next[n] != -1) {
                for (auto e : G[n]) {
                    int nxt = e.to;
                    if (nxt == par[n] || nxt == next[n])continue;
                    que.push({ nxt,d + 1 });
                }
                n = next[n];
                index[n] = idx++;
                depth[n] = d;
                head[n] = h;
            }
        }
    }
    void build() {
        dfs(0);
        assign_number();
    }
    int lca(int u, int v) {
        if (u == v)return u;
        if (depth[u] > depth[v])swap(u, v);
        while (depth[u] < depth[v]) {
            v = par[head[v]];
        }
        //if u and v begong to the same array
        if (head[u] == head[v]) {
            if (index[u] < index[v])return u;
            else return v;
        }
        else {
            u = par[head[u]];
            v = par[head[v]];
            return lca(u, v);
        }
    }
    vector<pair<int, int>>query(int u, int v) {
        vector<pair<int, int>>ret;
        if (depth[u] > depth[v])swap(u, v);
        while (depth[u] < depth[v]) {
            int l = index[head[v]], r = index[v] + 1;
            ret.push_back({ l,r });
            v = par[head[v]];
        }
        //if u and v begong to the same array
        if (head[u] == head[v]) {
            if (index[u] > index[v])swap(u, v);
            int l = index[u], r = index[v] + 1;
            ret.push_back({ l,r });
        }
        return ret;
    }
};
template<typename T>
struct SegmentTree {
    int n;
    T unit;
    vector<T>dat;
    function<T(T, T)> func;
    SegmentTree(const int N, T _unit, function<T(T, T)> _func)
        :unit(_unit), func(_func) {
        n = 1;
        //簡単のため、要素数を2のべき乗に
        while (n < N)n *= 2;
        dat.assign(2 * n, unit);
    }
    void update(int k, T a) {
        k += n - 1;//葉の節点
        dat[k] = a;
        //上りながら更新
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T _query(int a, int b, int k, int l, int r) {
        //[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す
        if (r <= a || b <= l)return unit;
        //[a,b)が[l,r)を完全に含んでいれば、この節点の値
        if (a <= l && r <= b)return dat[k];
        else {
            int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    //[a,b)
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }
};
//auto f = [](int a, int b) {return a + b; };
//SegmentTree<int>seg(N,0,f);
const int SIZE = 350;
ll C[200010], A[200010];
int who[200010];
int par[201010];
//[l,r)
int calc_par(int l, int r,HeavyLightDecomposition<int>&hl) {
    int p = A[l];
    int idx = l;
    while (idx < r) {
        if (idx%SIZE == 0 && idx + SIZE <= r) {
            p = hl.lca(p, par[idx / SIZE]);
            idx += SIZE;
        }
        else {
            p = hl.lca(p, A[idx]);
            idx++;
        }
    }
    return p;
}
int N,K;
int update(int idx,HeavyLightDecomposition<int>&hl) {
    int i = idx / SIZE;
    par[i] = A[i*SIZE];
    FOR(j, i*SIZE, i*SIZE + SIZE) {
        if (j >= K)break;
        par[i] = hl.lca(par[i], A[j]);
    }
    return par[i];
}
void solve() {
    cin >> N;
    int  Q; cin >> K >> Q;
    Graph<int>G(N);
    REP(i, N)cin >> C[i];
    REP(i, K) {
        cin >> A[i];
        A[i]--;
        who[A[i]] = i;
    }
    REP(i, N - 1) {
        int u, v; cin >> u >> v;
        u--, v--;
        if (u > v)swap(u, v);
        edge<int> e(v);
        G[u].push_back(e);
        edge<int>e2(u);
        G[v].push_back(e2);
    }
    auto f = [](int a, int b) {return max(a, b); };
    SegmentTree<int>seg(N, 0, f);
    //REP(i, N)seg.update(i, C[i]);
    HeavyLightDecomposition<int>hl(G);
    REP(i, N)seg.update(hl.index[i], C[i]);
    int cnt = (K + SIZE - 1) / SIZE;
    REP(i, cnt) {
        par[i] = A[i * SIZE];
        REP(j, SIZE) {
            int v = i * SIZE + j;
            if (v >= K)break;
            int p = hl.lca(par[i], A[v]);
            par[i] = p;
        }
    }
    //REP(i, cnt) {
    //  cout << i * SIZE << " " << i * SIZE + SIZE << ":" << par[i]+1 << endl;
    //}
    REP(_, Q) {
        int T; cin >> T;
        if (T == 2) {
            int l, r; cin >> l >> r;
            l--, r;
            int p = calc_par(l, r,hl);
            vector<pii>ps = hl.query(0, p);
            int res = 0;
            //cerr << "par:" << p + 1 << endl;
            for (auto pp : ps) {
                //cerr << pp.first+1 << " " << pp.second+1 << endl;
                res = max(res, seg.query(pp.first, pp.second));
            }
            //cerr << "par:" << p + 1 << endl;
            //int res = seg.query(0, p + 1);
            print(res);
        }
        else {
            int x, y; cin >> x >> y;
            x--; y--;
            A[x] = y;
            update(x,hl);
            //seg.update(hl.index[x], C[A[x]]);
        }
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    //int q; cin >> q;
    //while (q--)
    solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0