結果
| 問題 |
No.1030 だんしんぐぱーりない
|
| コンテスト | |
| ユーザー |
 jupiro
|
| 提出日時 | 2020-04-17 22:50:26 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 237 ms / 2,000 ms |
| コード長 | 6,381 bytes |
| コンパイル時間 | 1,576 ms |
| コンパイル使用メモリ | 135,112 KB |
| 実行使用メモリ | 29,184 KB |
| 最終ジャッジ日時 | 2024-10-03 14:34:33 |
| 合計ジャッジ時間 | 8,394 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
struct LCA {
static const int BITLEN_MAX = 20;
vector<int> parent[BITLEN_MAX];
vector<int> depth;
int bitlen;
LCA() {}
LCA(int N, vector<vector<int>> edges, int root) { initialize(N, edges, root); }
void initialize(int N, vector<vector<int>>& edges, int root) {
bitlen = 1;
while ((1 << bitlen) < N) bitlen += 1;
for (int i = 0; i < bitlen; i++) parent[i].resize(N);
depth.resize(N, -1);
dfs(root, -1, 0, edges);
for (int k = 0; k < bitlen - 1; k++) {
for (int v = 0; v < N; v++) {
if (depth[v] == -1) continue;
if (parent[k][v] < 0) {
parent[k + 1][v] = -1;
}
else {
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
void dfs(int v, int p, int d, vector<vector<int>>& edges) {
parent[0][v] = p;
depth[v] = d;
for (auto u : edges[v]) {
if (u != p) dfs(u, v, d + 1, edges);
}
}
int calc_lca(int u, int v) {
//cout << u << " " << v << endl;
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < bitlen; k++) {
if (((depth[v] - depth[u]) >> k) & 1) v = parent[k][v];
}
if (u == v) return u;
for (int k = bitlen - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int calc_dist(int u, int v) {
int l = calc_lca(u, v);
return depth[u] + depth[v] - depth[l] * 2;
}
};
vector<int> dep;
LCA lca;
template< typename Monoid >
struct SegmentTree {
using F = function< Monoid(Monoid, Monoid) >;
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid& M1) : f(f), M1(M1) {
sz = 1;
while (sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid& x) {
seg[k + sz] = x;
}
void build() {
for (int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid& x) {
k += sz;
seg[k] = x;
while (k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
if (a >= b) return M1;
for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) L = f(L, seg[a++]);
if (b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
};
struct HLD {
vector<int> sz, in, out, head, par;
vector<vector<int>> g;
HLD(vector<vector<int>>& _g) : g(_g), sz(_g.size()), in(_g.size()), out(_g.size()), head(_g.size()), par(_g.size()) {}
void dfs_sz(int cur, int pre) {
sz[cur] = 1;
for (int& next : g[cur]) {
if (next == pre) continue;
dfs_sz(next, cur);
par[next] = cur;
sz[cur] += sz[next];
if (sz[next] > sz[g[cur][0]]) swap(next, g[cur][0]);
}
}
void dfs_hld(int cur, int pre, int& idx) {
in[cur] = idx++;
for (int& next : g[cur]) {
if (next == pre) continue;
if (next == g[cur][0]) head[next] = head[cur];
else head[next] = next;
dfs_hld(next, cur, idx);
}
out[cur] = idx;
}
void build() {
dfs_sz(0, -1);
int idx = 0;
dfs_hld(0, -1, idx);
}
int lca(int u, int v) {
for (;; v = par[head[v]]) {
if (in[u] > in[v]) swap(u, v);
if (head[u] == head[v]) return u;
}
}
};
ll f1(ll a, ll b) {
if (b == INF) return a;
if (a == INF) return b;
return lca.calc_lca(a, b);
}
vector<vector<int>> g;
ll f2(ll a, ll b) {
return max(a, b);
}
int main()
{
/*
cin.tie(nullptr);
ios::sync_with_stdio(false);
*/
ll N, K, Q; scanf("%lld %lld %lld", &N, &K, &Q);
vector<ll> C(N); for (int i = 0; i < N; i++) scanf("%lld", &C[i]);
vector<ll> A(K); for (int i = 0; i < K; i++) scanf("%lld", &A[i]), A[i]--;
g.resize(N);
for (int i = 0; i < N - 1; i++) {
int u, v; scanf("%d %d", &u, &v);
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
lca.initialize(N, g, 0);
HLD hld(g);
hld.build();
SegmentTree<ll> seg1(K, f1, INF);
for (int i = 0; i < K; i++) seg1.set(i, A[i]);
seg1.build();
SegmentTree<ll> seg2(N + 1, f2, 0);
for (int i = 0; i < N; i++) seg2.set(hld.in[i], C[i]);
seg2.build();
while (Q--) {
int t; scanf("%d", &t);
if (t == 1) {
int x, y; scanf("%d %d", &x, &y);
x--; y--;
seg1.update(x, y);
}
else {
int l, r; scanf("%d %d", &l, &r);
l--;
int idx = seg1.query(l, r);
ll res = 0;
int u = 0;
int v = idx;
for (;; v = hld.par[hld.head[v]]) {
if (hld.head[u] == hld.head[v]) {
chmax(res, seg2.query(hld.in[u], hld.in[v] + 1));
break;
}
else {
chmax(res, seg2.query(hld.in[hld.head[v]], hld.in[v] + 1));
}
}
printf("%lld\n", res);
}
}
return 0;
}