P4315 月下“毛景树”(树链剖分)
P4315 月下“毛景树”(树链剖分)
简述: 边权转点权(在dfs1处转换) 把一条边权赋值在深度更深的上
需要实现对单边权的染色 , 路径边权的染色 , 路径边权的增加 , 路径边权的最大值查询
边权转点权后查询路径最值, u 和 v 的 lca的权值是它上一条边的权值，并不属于 u-v这条路径，所以我们在退出 top[u]!= top[v]这层循环，进行最后一次操作时应将 u的DFS 序加上 1 ，这样就可以忽略 lca 这个点了(记住如果循环结束后u=v要 直接return)。
有两种修改操作，所以需要两个懒标记，并且在下传标记时，要先实行染色标记，再实行增值标记(与区间乘加操作相同)。
Code
#include <bits/stdc++.h>
using namespace std;
#define re(a, b, c) for (int a = (b), LEN = (c); a <= LEN; ++a)
#define er(a, b, c) for (int a = (b), LEN = (c); a >= LEN; --a)
#define endl '\n'
using i64 = long long;
const int inf = INT_MIN;
// using i128=__int128;
template <typename T>
struct tree_chain {
int n, root;
vector<int> dfn, fa, son, dep, top, sz;
vector<T> val, old;
tree_chain(const vector<vector<pair<int, T>>> &adj, int _n, int _root) : n(_n), root(_root) {
dfn.resize(n), fa.resize(n), son.assign(n, -1), old.resize(n);
dep.resize(n), top.resize(n), sz.resize(n), val.resize(n);
dfs1(adj, root, -1, 1), dfs2(adj, root, root);
}
void dfs1(const vector<vector<pair<int, T>>> &adj, int now, int fath, int depth) {
dep[now] = depth;
fa[now] = fath;
sz[now] = 1;
int max_son = -1;
for (auto [v, c] : adj[now]) {
if (v == fath) continue;
old[v] = c;//边权转点权
dfs1(adj, v, now, depth + 1), sz[now] += sz[v]; // this position can solve edge value
if (sz[v] > max_son) son[now] = v, max_son = sz[v];
}
}
void dfs2(const vector<vector<pair<int, T>>> &adj, int now, int top_id) {
static int tot = -1;
dfn[now] = ++tot, val[tot] = old[now], top[now] = top_id;
if (son[now] == -1) return;
dfs2(adj, son[now], top_id);
for (auto [v, c] : adj[now])
if (v != fa[now] and v != son[now]) dfs2(adj, v, v);
}
int lca(int u, int v) {
while (top[u] != top[v]) dep[top[u]] >= dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
/*
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
do something...
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
do something...
*/
}; // the idx of begin is 0 ,notice use dfn when?
class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
i64 maxx = inf;
i64 add = 0;
i64 ass = inf;
void apply(int l, int r, i64 v) {
// make v become node(tag,data) in modify
add += v;
maxx += v;
}
void init(i64 v) {
// in build_tree init
maxx = v;
add = 0;
ass = inf;
}
};
node unite(const node &a, const node &b) const {
node res;
res.maxx = max(a.maxx, b.maxx);
return res;
}
// about x: left son is x+1 , right son is x+((mid-l+1)<<1) ;
inline void push_down(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
// push from x into (x + 1) and z
if (tree[x].ass >= 0) {
tree[x + 1].maxx = tree[x + 1].ass = tree[x].ass;
tree[z].maxx = tree[z].ass = tree[x].ass;
tree[x + 1].add = tree[z].add = 0;
tree[x].ass = inf;
}
if (tree[x].add != 0) {
tree[x + 1].apply(l, y, tree[x].add);
tree[z].apply(y + 1, r, tree[x].add);
tree[x].add = 0;
}
}
int n;
vector<node> tree;
inline void push_up(int x, int z) { tree[x].maxx = max(tree[x + 1].maxx, tree[z].maxx); }
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
push_up(x, z);
}
template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].init(v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v);
build(z, y + 1, r, v);
push_up(x, z);
}
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push_down(x, l, r);
node res{};
if (rr <= y)
res = get(x + 1, l, y, ll, rr);
else {
if (ll > y)
res = get(z, y + 1, r, ll, rr);
else
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
push_up(x, z);
return res;
}
template <typename M>
void modify(int x, int l, int r, int ll, int rr, const M &v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push_down(x, l, r);
if (ll <= y) modify(x + 1, l, y, ll, rr, v);
if (rr > y) modify(z, y + 1, r, ll, rr, v);
push_up(x, z);
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename M>
void modify(int ll, int rr, const M &v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v);
}
void assign(int x, int l, int r, int ll, int rr, i64 v) {
if (ll <= l && r <= rr) {
tree[x].maxx = tree[x].ass = v;
tree[x].add = 0;
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push_down(x, l, r);
if (ll <= y)
assign(x + 1, l, y, ll, rr, v);
if (rr > y)
assign(z, y + 1, r, ll, rr, v);
push_up(x, z);
}
}; // root's idx is 0 and the begin of vector is also 0;
// don't forget idx is from 0 to n-1 (equal [--x,--y]) when ask;
int n;
i64 ans(tree_chain<i64> &ch, segtree &t, int x, int y) {
i64 res = 0;
while (ch.top[x] != ch.top[y]) {
if (ch.dep[ch.top[x]] < ch.dep[ch.top[y]]) swap(x, y);
res = max(res, t.get(ch.dfn[ch.top[x]], ch.dfn[x]).maxx);
x = ch.fa[ch.top[x]];
}
if (ch.dep[x] > ch.dep[y]) swap(x, y);
if (x == y) return res;//return
res = max(res, t.get(ch.dfn[x] + 1, ch.dfn[y]).maxx);
return res;
}
void add(tree_chain<i64> &ch, segtree &t, int x, int y, i64 w) {
while (ch.top[x] != ch.top[y]) {
if (ch.dep[ch.top[x]] < ch.dep[ch.top[y]]) swap(x, y);
t.modify(ch.dfn[ch.top[x]], ch.dfn[x], w);
x = ch.fa[ch.top[x]];
}
if (ch.dep[x] > ch.dep[y]) swap(x, y);
if (x == y) return;
t.modify(ch.dfn[x] + 1, ch.dfn[y], w);
}
void assign(tree_chain<i64> &ch, segtree &t, int x, int y, i64 w) {
while (ch.top[x] != ch.top[y]) {
if (ch.dep[ch.top[x]] < ch.dep[ch.top[y]]) swap(x, y);
t.assign(0, 0, n - 1, ch.dfn[ch.top[x]], ch.dfn[x], w);
x = ch.fa[ch.top[x]];
}
if (ch.dep[x] > ch.dep[y]) swap(x, y);
if (x == y) return;
t.assign(0, 0, n - 1, ch.dfn[x] + 1, ch.dfn[y], w);
};
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
cin >> n;
vector<vector<pair<int, i64>>> adj(n);
vector<pair<int, int>> g(n);
for (int i = 1, x, y, v; i < n; ++i) {
cin >> x >> y >> v;
--x, --y;
g[i] = {x, y};
adj[x].emplace_back(y, v);
adj[y].emplace_back(x, v);
}
tree_chain<i64> ch(adj, n, 0);
segtree t(ch.val);
string op;
while (cin >> op) {
if (op == "Stop") break;
int u, v;
i64 w;
if (op == "Change")
cin >> u >> w, assign(ch, t, g[u].first, g[u].second, w);
else if (op == "Cover")
cin >> u >> v >> w, assign(ch, t, --u, --v, w);
else if (op == "Add")
cin >> u >> v >> w, add(ch, t, --u, --v, w);
else
cin >> u >> v, cout << ans(ch, t, --u, --v) << endl;
}
return 0;
}
