題目描述

給你一棵樹，兩種操作。
修改邊權，查找邊權的最大值。

分析

我們都知道，樹鏈剖分能夠維護點權。
而且每一條邊只有一個，且唯一對應一個兒子節點，那么就把信息放到這個兒子節點上。
注意，lca的信息不能算到，也就是當查詢到了\(top[u]=top[v]\)的時候，要從\(idx[u]+1\)到\(v\)的查詢，因為\(idx[u]\)為lca。

代碼

#include <bits/stdc++.h> #define ms(a, b) memset(a, b, sizeof(a)) #define ll long long #define ull unsigned long long #define ms(a, b) memset(a, b, sizeof(a)) #define inf 0x3f3f3f3f #define db double #define Pi acos(-1) #define eps 1e-8 #define N 200005 using namespace std; template <typename T> void read(T &x) {x = 0; T fl = 1; char ch = 0;for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);x *= fl; } template <typename T> void write(T x) {if (x < 0) x = -x, putchar('-');if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct edge {int to, nt, w; }E[N << 1]; int H[N], top[N], dep[N], son[N], idx[N], fa[N], sz[N], val[N], a[N], U[N], V[N]; int cnt, tot = 0, n; void add_edge(int u, int v, int w) {E[++ cnt] = (edge){v, H[u], w}; H[u] = cnt; } struct Segment_Tree {#define lc (nod << 1)#define rc (nod << 1 | 1)struct node {int mx, l, r;}tr[N << 2];void pushup(int nod) { tr[nod].mx = max(tr[lc].mx, tr[rc].mx); }void build(int nod, int l, int r, int *a) {tr[nod].l = l, tr[nod].r = r; tr[nod].mx = -inf;if (l == r) { tr[nod].mx = a[l]; return; }int mid = (l + r) >> 1;build(lc, l, mid, a); build(rc, mid + 1, r, a);pushup(nod);}void update(int nod, int k, int val) {int l = tr[nod].l, r = tr[nod].r;if (l == r) { tr[nod].mx = val; return; }int mid = (l + r) >> 1;if (k <= mid) update(lc, k, val); else update(rc, k, val);pushup(nod);}int query(int nod, int ql, int qr) {int l = tr[nod].l, r = tr[nod].r;if (ql <= l && r <= qr) return tr[nod].mx; int mid = (l + r) >> 1, res = -inf;if (ql <= mid) res = max(res, query(lc, ql, qr));if (qr > mid) res = max(res, query(rc, ql, qr));return res;} }sgt; void dfs1(int u, int ft, int dp) {dep[u] = dp; fa[u] = ft; sz[u] = 1;int maxson = -1;for (int e = H[u]; e; e = E[e].nt) {int v = E[e].to; if (v == fa[u]) continue;dfs1(v, u, dp + 1);a[v] = E[e].w; sz[u] += sz[v];if (sz[v] > maxson) maxson = sz[v], son[u] = v;} } void dfs2(int u, int tp) {top[u] = tp; idx[u] = ++ tot; val[tot] = a[u];if (!son[u]) return; dfs2(son[u], tp);for (int e = H[u]; e; e = E[e].nt) { int v = E[e].to; if (v == fa[u] || v == son[u]) continue; dfs2(v, v); } } char opt[10]; int query_chain(int u, int v) {int res = -inf;while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) swap(u, v);res = max(res, sgt.query(1, idx[top[u]], idx[u]));u = fa[top[u]];}if (dep[u] > dep[v]) swap(u, v);res = max(res, sgt.query(1, idx[u] + 1, idx[v]));return res; } int main() {read(n);for (int i = 1; i < n; i ++) {int u, v, w; read(u); read(v); read(w);add_edge(u, v, w); add_edge(v, u, w);U[i] = u; V[i] = v;}dfs1(1, 0, 1); dfs2(1, 1);sgt.build(1, 1, n, val);while (scanf("%s", opt) != EOF) {if (opt[0] == 'D') return 0;int x, y; read(x); read(y);if (opt[0] == 'Q') writeln((x != y)? query_chain(x, y): 0);else {int u = U[x], v = V[x]; if (fa[v] == u) swap(u, v); sgt.update(1, idx[u], y);}}return 0; }

轉載于:https://www.cnblogs.com/chhokmah/p/10653415.html

總結

以上是生活随笔為你收集整理的[SPOJ375]QTREE - Query on a tree【树链剖分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。