結果
| 問題 |
No.1030 だんしんぐぱーりない
|
| コンテスト | |
| ユーザー |
 tsutaj
|
| 提出日時 | 2020-04-17 22:58:40 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 259 ms / 2,000 ms |
| コード長 | 6,305 bytes |
| コンパイル時間 | 1,498 ms |
| コンパイル使用メモリ | 119,968 KB |
| 実行使用メモリ | 27,368 KB |
| 最終ジャッジ日時 | 2024-10-03 14:53:44 |
| 合計ジャッジ時間 | 8,675 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
// @category セグメント木 (Segment Tree)
// @title セグメント木 (Segment Tree)
// 抽象 SegmentTree (0-indexed・一点更新・区間取得)
template <typename MonoidType>
struct SegmentTree {
using Function = function< MonoidType(MonoidType, MonoidType) >;
// node, identity element
int n, orig_n;
vector<MonoidType> node;
MonoidType E0;
// update / combine function
Function upd_f, cmb_f;
void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
if(v != vector<MonoidType>()) m = v.size();
n = 1; while(n < m) n *= 2;
node = vector<MonoidType>(2*n-1, E0);
if(v != vector<MonoidType>()) {
for(int i=0; i<m; i++) {
node[n-1+i] = v[i];
}
for(int i=n-2; i>=0; i--) {
node[i] = cmb_f(node[2*i+1], node[2*i+2]);
}
}
}
// initialize
SegmentTree() {}
SegmentTree(int n_, MonoidType E0_,
Function upd_f_, Function cmb_f_,
vector<MonoidType> v = vector<MonoidType>()) :
E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
build(n_, v);
orig_n = n_;
}
// update k-th element (applied value: x)
void update(int k, MonoidType x) {
k += n - 1;
node[k] = upd_f(node[k], x);
while(k > 0) {
k = (k - 1) / 2;
node[k] = cmb_f(node[2*k+1], node[2*k+2]);
}
}
// range query for [a, b)
// 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406
MonoidType query(int a, int b) {
assert(a >= 0 and a < b and b <= orig_n);
MonoidType vl = node[n-1+a], vr = node[n-1+b-1];
for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
if(l & 1) vl = cmb_f(vl, node[(l++)-1]);
if(r & 1) vr = cmb_f(node[(--r)-1], vr);
}
return cmb_f(vl, vr);
}
};
// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
int from, to;
T cost;
Edge(int s, T d = 1) : to(s), cost(d) {}
Edge(int f, int s, T d) : from(f), to(s), cost(d) {}
bool operator<(const Edge &e) const {
return cost < e.cost;
}
bool operator>(const Edge &e) const {
return cost > e.cost;
}
};
template <typename T = int>
using Graph = vector< vector< Edge<T> > >;
// 最小共通先祖 (Lowest Common Ancestor, LCA) を求める
// Verified: AOJ GRL_5_C (Lowest Common Ancestor)
template <typename T>
struct TreeLCA {
public:
int const MAX_LOG_V;
vector< vector< Edge<T> > > G;
int root, vn;
vector< vector<int> > parent;
vector<int> depth;
// constructor (Graph, root)
TreeLCA(vector< vector< Edge<T> > > &_G, int _r) :
MAX_LOG_V(20), G(_G), root(_r), vn(G.size()),
parent(MAX_LOG_V, vector<int>(vn, 0)), depth(vn, -1)
{ depth[root] = 0; init(vn); }
void dfs(int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for(int i=0; i<G[v].size(); i++) {
if(depth[ G[v][i].to ] >= 0) continue;
if(G[v][i].to != p) dfs(G[v][i].to, v, d+1);
}
}
void init(int V) {
dfs(root, -1, 0);
for(int k=0; k+1 < MAX_LOG_V; k++) {
for(int v=0; v < V; v++) {
if(parent[k][v] < 0) parent[k+1][v] = -1;
else parent[k+1][v] = parent[k][parent[k][v]];
}
}
}
// u と v の最小共通祖先
int lca(int u, int v) {
if(depth[u] > depth[v]) swap(u, v);
for(int k=0; k < MAX_LOG_V; k++) {
if((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if(u == v) return u;
for(int k=MAX_LOG_V - 1; k>=0; k--) {
if(parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
// u と v のパスの長さ (LCA を使って計算)
int dist(int u, int v) {
int anc = lca(u, v);
return depth[u] + depth[v] - 2 * depth[anc];
}
};
int main() {
int N, K, Q; scanf("%d%d%d", &N, &K, &Q);
vector<int> C(N), M(N);
for(int i=0; i<N; i++) scanf("%d", &C[i]);
vector<int> A(K);
for(int i=0; i<K; i++) scanf("%d", &A[i]), A[i]--;
vector< vector< Edge<> > > G(N);
for(int i=0; i+1<N; i++) {
int u, v; scanf("%d%d", &u, &v);
u--; v--;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
auto dfs = [&](auto &&self, int cur, int par) -> void {
chmax(M[cur], C[cur]);
for(auto e : G[cur]) {
int to = e.to;
if(to == par) continue;
chmax(M[to], M[cur]);
self(self, to, cur);
}
};
dfs(dfs, 0, -1);
TreeLCA<int> lc(G, 0);
SegmentTree<int> seg(K, -1,
[](int a, int b) { return b; },
[&lc](int a, int b) { return lc.lca(a, b); },
A);
while(Q--) {
int t; scanf("%d", &t);
if(t == 1) {
int x, y; scanf("%d%d", &x, &y);
x--; y--;
seg.update(x, y);
}
if(t == 2) {
int l, r; scanf("%d%d", &l, &r); l--;
printf("%d\n", M[seg.query(l, r)]);
}
}
return 0;
}