正題

luogu 3976

---

題目大意

給你一棵樹，每個點有一個權值s

現在給你一條路徑，讓你選擇兩個點x,y，使y在x后面，且$s_y?s_x$最大

然后該路勁上所有點權值加v

---

解題思路

樹鏈剖分

在線段樹上維護從左到右和從右到左的最大價值

每次查詢，如果是跳開頭就找最小的，如果是跳結尾就找最大的

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 500100 using namespace std; int n, x, y, z, w, m, tot; int s[N], v[N], ww[N], fa[N], fv[N], hs[N], dep[N], anc[N], head[N]; struct rec {int to, next; }a[N<<1]; struct node {int mn, mx, ml, mr; }; struct Tree {int mx[N<<2], mn[N<<2], ml[N<<2], mr[N<<2], lazy[N<<2];#define ls x*2#define rs x*2+1void addd(int x, int y){lazy[x] += y;mn[x] += y;mx[x] += y;}void down(int x){if (lazy[x]){addd(ls, lazy[x]);addd(rs, lazy[x]);lazy[x] = 0;}return;}void up(int x){mn[x] = min(mn[ls], mn[rs]);mx[x] = max(mx[ls], mx[rs]);ml[x] = max(mx[rs] - mn[ls], max(ml[ls], ml[rs]));//從左到右和從右到左的最大價值mr[x] = max(mx[ls] - mn[rs], max(mr[ls], mr[rs]));}void build(int x, int l, int r){if (l == r){mn[x] = mx[x] = ww[fv[l]];return;}int mid = l + r >> 1;build(ls, l, mid);build(rs, mid + 1, r);up(x); return;}void add(int x, int L, int R, int l, int r, int y){if (L == l && R == r){addd(x, y);return;}int mid = L + R >> 1;down(x);if (r <= mid) add(ls, L, mid, l, r, y);else if (l > mid) add(rs, mid + 1, R, l, r, y);else add(ls, L, mid, l, mid, y), add(rs, mid + 1, R, mid + 1, r, y);up(x);return;}node ask(int x, int L, int R, int l, int r)//查詢區間的各個值{if (L == l && R == r) return (node){mn[x], mx[x], ml[x], mr[x]};int mid = L + R >> 1;down(x);if (r <= mid) return ask(ls, L, mid, l, r);else if (l > mid) return ask(rs, mid + 1, R, l, r);else{node x1 = ask(ls, L, mid, l, mid);node x2 = ask(rs, mid + 1, R, mid + 1, r);node x3;x3.mn = min(x1.mn, x2.mn);x3.mx = max(x1.mx, x2.mx);x3.ml = max(max(x1.ml, x2.ml), x2.mx - x1.mn);x3.mr = max(max(x1.mr, x2.mr), x1.mx - x2.mn);return x3;}} }T; void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot; } void dfs1(int x) {s[x] = 1;for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa[x]){fa[a[i].to] = x;dep[a[i].to] = dep[x] + 1;dfs1(a[i].to);s[x] += s[a[i].to];if (s[a[i].to] > s[hs[x]]) hs[x] = a[i].to;}return; } void dfs2(int x, int y) {anc[x] = y;v[x] = ++w;fv[w] = x;if (hs[x]) dfs2(hs[x], y);for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa[x] && a[i].to != hs[x])dfs2(a[i].to, a[i].to);return; } void solve(int x, int y, int z) {int fx = anc[x], fy = anc[y];while (fx != fy){if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);T.add(1, 1, n, v[fx], v[x], z);x = fa[fx];fx = anc[x];}if (dep[x] > dep[y]) swap(x, y);T.add(1, 1, n, v[x], v[y], z);return; } int ask(int x, int y) {int fx = anc[x], fy = anc[y], bg = 1000000000, ed = 0, ans = 0;while (fx != fy){if (dep[fx] > dep[fy]){node x1 = T.ask(1, 1, n, v[fx], v[x]);ans = max(ans, max(x1.mr, x1.mx - bg));//計算結果bg = min(bg, x1.mn);//最小的x = fa[fx];fx = anc[x];}else{node x1 = T.ask(1, 1, n, v[fy], v[y]);ans = max(ans, max(x1.ml, ed - x1.mn));ed = max(ed, x1.mx);y = fa[fy];fy = anc[y];}}if (dep[x] > dep[y]){node x1 = T.ask(1, 1, n, v[y], v[x]);ans = max(ans, max(x1.mr, x1.mx - bg));bg = min(bg, x1.mn);}else{node x1 = T.ask(1, 1, n, v[x], v[y]);ans = max(ans, max(x1.ml, ed - x1.mn));ed = max(ed, x1.mx);}return max(ed - bg, ans); } int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &ww[i]);for (int i = 1; i < n; ++i){scanf("%d%d", &x, &y);add(x, y);add(y, x);}dep[1] = fa[1] = 1;dfs1(1);dfs2(1, 1);T.build(1, 1, n);scanf("%d", &m);for (int i = 1; i <= m; ++i){scanf("%d%d%d", &x, &y, &z);printf("%d\n", ask(x, y));solve(x, y, z);}return 0; }

總結

以上是生活随笔為你收集整理的【树链剖分】旅游（luogu 3976）的全部內容，希望文章能夠幫你解決所遇到的問題。

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