毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：
Change k w：将第k条树枝上毛毛果的个数改变为w个。
Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：
Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
第一行一个正整数N。
接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
对于毛毛虫的每个询问操作，输出一个答案。
输入 #1复制
4 1 2 8 1 3 7 3 4 9 Max 2 4 Cover 2 4 5 Add 1 4 10 Change 1 16 Max 2 4 Stop输出 #1复制
9 161<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
原来区间覆盖可以直接标记的，第一次写的时候乘0再加，写的麻烦又难调QAQ
解法：
除去树剖部分，就是线段树的区间覆盖，区间加，区间最大值，区间覆盖的优先级是大于区间加的，Pushdown的过程中先更新覆盖部分，并且把加法的lazy置为0。边权可以用深度较大的点权来表示，所以更新同一条重链的时候，左区间需要+1。这些是我写的过程中遇到的问题，剩下就是改板子啦。
Accepted code
#include<bits/stdc++.h> #include<unordered_map> using namespace std; #define sc scanf #define ls rt << 1 #define rs ls | 1 #define Min(x, y) x = min(x, y) #define Max(x, y) x = max(x, y) #define ALL(x) (x).begin(),(x).end() #define SZ(x) ((int)(x).size()) #define pir pair <int, int> #define MK(x, y) make_pair(x, y) #define MEM(x, b) memset(x, b, sizeof(x)) #define MPY(x, b) memcpy(x, b, sizeof(x)) #define lowbit(x) ((x) & -(x)) #define P2(x) ((x) * (x)) typedef long long ll; const int Mod = 1e9 + 7; const int N = 1e5 + 100; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; inline ll dpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % Mod; b >>= 1; t = (t*t) % Mod; }return r; } inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t); b >>= 1; t = (t*t); }return r; } // 存图 vector <pir> G[N << 1]; int fz[N], son[N], sz[N]; int idx[N], dfn; int dep[N], top[N]; int wt[N], ev[N], n, q; pir a[N]; char op[10]; void dfs1(int x, int fa, int dist) { fz[x] = fa; // 父亲 dep[x] = dist; //深度 sz[x] = 1; // 子树大小 int mx = 0; // 重儿子个数 for (auto it : G[x]) { int v = it.second; int w = it.first; if (v == fa) continue; wt[v] = w; dfs1(v, x, dist + 1); sz[x] += sz[v]; if (sz[v] > mx) mx = sz[v], son[x] = v; } } void dfs2(int x, int topfz) { idx[x] = ++dfn; // 重新编号 top[x] = topfz; ev[dfn] = wt[x]; if (!son[x]) return; dfs2(son[x], topfz); for (auto it : G[x]) { int v = it.second; if (v != fz[x] && v != son[x]) dfs2(v, v); } } // 线段树 int mx[N * 4]; int lzy[N * 4], add[N * 4]; // 覆盖，加 void Build(int rt, int L, int R) { lzy[rt] = -1; if (L == R) { mx[rt] = ev[L]; // 这个映射关系搞清楚，是重新编号后的点 return; } int mid = (L + R) >> 1; Build(ls, L, mid); Build(rs, mid + 1, R); mx[rt] = max(mx[ls], mx[rs]); } void Pushdown(int rt) { if (lzy[rt] != -1) { // 优先覆盖 add[ls] = add[rs] = 0; // 注意清0哦 mx[ls] = mx[rs] = lzy[rt]; lzy[ls] = lzy[rs] = lzy[rt]; lzy[rt] = -1; } if (add[rt]) { // 区间加 mx[ls] += add[rt], mx[rs] += add[rt]; add[ls] += add[rt], add[rs] += add[rt]; add[rt] = 0; } } void Update(int rt, int L, int R, int l, int r, int w) { // 区间覆盖 if (L >= l && R <= r) { mx[rt] = w; lzy[rt] = w, add[rt] = 0; return; } Pushdown(rt); int mid = (L + R) >> 1; if (mid >= l) Update(ls, L, mid, l, r, w); if (mid < r) Update(rs, mid + 1, R, l, r, w); mx[rt] = max(mx[ls], mx[rs]); } void Add(int rt, int L, int R, int l, int r, int w) { // 区间加 if (L >= l && R <= r) { mx[rt] += w; add[rt] += w; return; } Pushdown(rt); int mid = (L + R) >> 1; if (mid >= l) Add(ls, L, mid, l, r, w); if (mid < r) Add(rs, mid + 1, R, l, r, w); mx[rt] = max(mx[ls], mx[rs]); } int Query(int rt, int L, int R, int l, int r) { // 区间查询 if (L >= l && R <= r) return mx[rt]; Pushdown(rt); int mid = (L + R) >> 1; int tot = 0; if (mid >= l) Max(tot, Query(ls, L, mid, l, r)); if (mid < r) Max(tot, Query(rs, mid + 1, R, l, r)); return tot; } void Range_Update(int x, int y, int w) { while (top[x] != top[y]) { // 先轻链 if (dep[top[x]] < dep[top[y]]) swap(x, y); Update(1, 1, n, idx[top[x]], idx[x], w); x = fz[top[x]]; } if (dep[x] > dep[y]) // 后重链 swap(x, y); Update(1, 1, n, idx[x] + 1, idx[y], w); } void Range_Add(int x, int y, int w) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); Add(1, 1, n, idx[top[x]], idx[x], w); x = fz[top[x]]; } if (dep[x] > dep[y]) swap(x, y); Add(1, 1, n, idx[x] + 1, idx[y], w); } int Range_Query(int x, int y) { // 都一样啦 int tot = 0; while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); Max(tot, Query(1, 1, n, idx[top[x]], idx[x])); x = fz[top[x]]; } if (dep[x] > dep[y]) swap(x, y); Max(tot, Query(1, 1, n, idx[x] + 1, idx[y])); return tot; } int main() { cin >> n; for (int i = 1; i < n; i++) { int u, v, w; sc("%d %d %d", &u, &v, &w); G[u].push_back({ w, v }); G[v].push_back({ w, u }); a[i] = { u, v }; // 保存边的编号 } dfs1(1, 0, 1); dfs2(1, 1); Build(1, 1, n); // 树剖+建树 while (sc("%s", op) && op[0] != 'S') { int x, y, w; if (op[1] == 'h') { sc("%d %d", &x, &w); int u = a[x].first; int v = a[x].second; if (dep[u] < dep[v]) // 度数较大的点来表示边 swap(u, v); Update(1, 1, n, idx[u], idx[u], w); } else if (op[1] == 'o') { // 区间覆盖 sc("%d %d %d", &x, &y, &w); Range_Update(x, y, w); } else if (op[0] == 'A') { // 区间加 sc("%d %d %d", &x, &y, &w); Range_Add(x, y, w); } else { // 区间查询 sc("%d %d", &x, &y); printf("%d\n", Range_Query(x, y)); } } return 0; // 改数组大小!!!用pair记得改宏定义!!! }
