結果

問題 No.1030 だんしんぐぱーりない
ユーザー risujiroh
提出日時 2020-04-17 22:09:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 235 ms / 2,000 ms
コード長 5,636 bytes
コンパイル時間 2,958 ms
コンパイル使用メモリ 217,880 KB
最終ジャッジ日時 2025-01-09 20:08:25
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif
template <class T> struct tree {
struct edge {
int u, v;
T w;
};
int n;
vector<edge> es;
vector<vector<int>> g;
vector<int> pv, pe, sz, dep, vs, in, out, head;
vector<T> dist;
tree(int _n = 0) : n(_n), g(n) {}
void add(int u, int v, T w = 1) {
g[u].push_back(es.size()), g[v].push_back(es.size());
es.push_back({u, v, w});
}
int other(int id, int v) const { return es[id].u ^ es[id].v ^ v; }
void dfs(int v) {
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v]) continue;
int to = other(id, v);
assert(pv[to] == -1);
pv[to] = v, pe[to] = id;
dep[to] = dep[v] + 1, dist[to] = dist[v] + es[id].w;
dfs(to);
sz[v] += sz[to];
}
sort(begin(g[v]), end(g[v]), [&](int a, int b) {
return sz[other(a, v)] * (a != pe[v]) > sz[other(b, v)] * (b != pe[v]);
});
}
void build(int r = 0) {
assert((int)es.size() == n - 1);
pv.assign(n, -1), pe.resize(n), sz.resize(n), dep.resize(n), dist.resize(n);
pe[r] = -1, dep[r] = 0, dist[r] = 0;
dfs(r);
}
void dfs_hld(int v) {
in[v] = vs.size(), vs.push_back(v);
for (int id : g[v]) {
if (id == pe[v]) continue;
int to = other(id, v);
head[to] = to == other(g[v][0], v) ? head[v] : to;
dfs_hld(to);
}
out[v] = vs.size();
}
void build_hld(int r = 0) {
build(r);
vs.clear(), in.resize(n), out.resize(n), head.resize(n);
head[r] = r;
dfs_hld(r);
}
bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; }
int lca(int u, int v) const {
while (true) {
if (in[u] > in[v]) swap(u, v);
if (head[u] == head[v]) return u;
v = pv[head[v]];
}
}
int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
T len(int u, int v) const { return dist[u] + dist[v] - 2 * dist[lca(u, v)]; }
int la(int v, int d) const {
assert(0 <= d and d <= dep[v]);
while (dep[head[v]] > d) v = pv[head[v]];
return vs[in[head[v]] + (d - dep[head[v]])];
}
int next(int from, int to) const {
assert(from != to);
if (not anc(from, to)) return pv[from];
return la(to, dep[from] + 1);
}
vector<pair<int, int>> ascend(int from, int to) const {
vector<pair<int, int>> res;
while (head[from] != head[to]) {
res.emplace_back(in[from], in[head[from]]);
from = pv[head[from]];
}
if (from != to) res.emplace_back(in[from], in[to] + 1);
return res;
}
vector<pair<int, int>> descend(int from, int to) const {
if (from == to) return {};
if (head[from] == head[to]) return {{in[from] + 1, in[to]}};
auto res = descend(from, pv[head[to]]);
res.emplace_back(in[head[to]], in[to]);
return res;
}
template <class F> void run(int from, int to, F f, bool vertex = true) const {
int v = lca(from, to);
for (auto e : ascend(from, v)) f(e.first + 1, e.second);
if (vertex) f(in[v], in[v] + 1);
for (auto e : descend(v, to)) f(e.first, e.second + 1);
}
template <class Node> vector<Node> dp(int r = 0) {
build_hld(r);
vector<Node> lower(n - 1), upper(n - 1), res(n);
vector<vector<Node>> cum(n);
for (int t = n; t--; ) {
int v = vs[t], m = g[v].size() - (v != r);
cum[v].resize(m + 1);
for (int i = m; i--; ) cum[v][i] = lower[g[v][i]] + cum[v][i + 1];
if (v != r) lower[pe[v]] = cum[v][0].add(v, pe[v]);
}
for (int v : vs) {
Node cur = v != r ? upper[pe[v]] : Node();
for (int i = 0, m = cum[v].size() - 1; i < m; ++i) {
upper[g[v][i]] = (cur + cum[v][i + 1]).add(v, g[v][i]);
cur = cur + lower[g[v][i]];
}
res[v] = cur.add(v);
}
return res;
}
};
template <class T> struct segtree {
const int n;
vector<T> t;
segtree(int _n = 0) : n(_n), t(2 * n) {}
T& operator[](int i) { return t[n + i]; }
void build() { for (int i = n; i--; ) t[i] = t[2 * i] * t[2 * i + 1]; }
T fold(int l, int r) const {
T a, b;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) a = a * t[l++];
if (r & 1) b = t[--r] * b;
}
return a * b;
}
void set(int i, T a) {
t[i += n] = a;
while (i >>= 1) t[i] = t[2 * i] * t[2 * i + 1];
}
};
tree<int> g;
struct node {
int v = -1;
node operator*(node b) const {
if (v == -1) {
return b;
}
if (b.v == -1) {
return *this;
}
return {g.lca(v, b.v)};
}
};
struct maxi {
int v = -1;
maxi operator*(maxi b) const {
return {max(v, b.v)};
}
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, k, q;
cin >> n >> k >> q;
vector<int> c(n);
for (auto&& e : c) {
cin >> e;
}
vector<int> a(k);
for (auto&& e : a) {
cin >> e;
--e;
}
g = tree<int>(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g.add(u, v);
}
g.build_hld();
segtree<node> seg(k);
for (int i = 0; i < k; ++i) {
seg[i] = {a[i]};
}
seg.build();
segtree<maxi> mx(n);
for (int v = 0; v < n; ++v) {
mx[g.in[v]] = {c[v]};
}
mx.build();
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, y;
cin >> x >> y;
--x, --y;
seg.set(x, {y});
} else {
int l, r;
cin >> l >> r;
--l;
int res = -1;
DEBUG(seg.fold(l, r).v);
g.run(seg.fold(l, r).v, 0, [&](int ll, int rr) {
if (ll > rr) {
swap(ll, rr);
}
res = max(res, mx.fold(ll, rr).v);
});
cout << res << '\n';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0