洛谷P3178 [HAOI2015]树上操作
题目描述
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
输入格式
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
输出格式
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
#include <cstdio>#include <iostream>#define int long long#define lson(now) now << 1#define rson(now) now << 1|1const int maxx = 100010;using namespace std;int n, m, a[maxx], pre[maxx];inline int read(){int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 ch - '0';ch = getchar();}return x * f;}//-----------------------------------------------------------------------------------------struct tree{int lazy, sum, len;}t[maxx << 2];void push_up(int now){t[now].sum = t[lson(now)].sum t[rson(now)].sum;}void build(int now, int l, int r)//建线段树{t[now].len = r - l 1;//区间内元素的个数 if(l == r){t[now].sum = a[pre[l]];return; }int mid = (l r) >> 1;build(lson(now), l, mid);build(rson(now), mid 1, r);push_up(now);} void push_down(int now)//下穿懒惰标记 {if(t[now].lazy == 0) return;t[lson(now)].sum = t[now].lazy * t[lson(now)].len;t[rson(now)].sum = t[now].lazy * t[rson(now)].len;t[lson(now)].lazy = t[now].lazy;t[rson(now)].lazy = t[now].lazy;t[now].lazy = 0;}void updata(int now, int val, int nl, int nr, int l, int r)//nl，nr为当前节点区间 l,r要查询的区间， {if(nl >= l && nr <= r)//当前区间包含在要查询的区间内 {t[now].sum = t[now].len * val;t[now].lazy = val;return; } push_down(now);int mid = (nl nr) >> 1;if(l <= mid) updata(lson(now), val, nl, mid, l, r);if(r > mid) updata(rson(now), val, mid 1, nr, l, r);push_up(now);} int query(int now, int nl, int nr, int l, int r){if(l <= nl && r >= nr) return t[now].sum;push_down(now);int mid = (nl nr) >> 1, ans = 0;if(l <= mid) ans = query(lson(now), nl, mid, l, r);if(r > mid) ans = query(rson(now), mid 1, nr, l, r);return ans;}//------------------------------------------------------------struct egde{int u, v, w, nxt;}e[maxx << 1];int head[maxx], js;void add(int u, int v){e[ js].u = u;e[js].v = v;e[js].nxt = head[u];head[u] = js;}int fa[maxx], dep[maxx], size[maxx], son[maxx];//各个点的深度，父亲，子树大小，重儿子 void dfs1(int u, int f, int d)//当前点，父亲节点，深度 {fa[u] = f;dep[u] = d;size[u] = 1;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].v;if(v != f){dfs1(v, u, d 1);size[u] = size[v];if(!son[u]||size[son[u]] < size[v])//找重儿子 son[u] = v;}}}int top[maxx], pos[maxx], p;//记录节点的链顶，记录每个节点的位置 p位置 void dfs2(int u, int tp)//找链 u 当前节点 tp 链顶 {top[u] = tp;pos[u] = p; pre[p] = u;if(!son[u]) return;//叶节点dfs2(son[u], tp);for(int i = head[u]; i; i = e[i].nxt) {int v = e[i].v;if(v != son[u] && v != fa[u])dfs2(v, v);}}void change(int x, int y, int c){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) swap(x, y);updata(1, c, 1, n, pos[top[x]], pos[y]); x = fa[top[x]];}if(dep[x] > dep[y]) swap(x, y);updata(1, c, 1, n, pos[x], pos[y]); }int asksum(int x, int y){int ans = 0;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) swap(x, y);ans = query(1, 1, n, pos[top[x]], pos[x]);x = fa[top[x]];}if(dep[x] > dep[y]) swap(x, y);ans = query(1, 1, n, pos[x], pos[y]);return ans;}signed main(){ n = read(); m = read(); for(int i = 1; i <= n; i ) a[i] = read(); for(int i = 1; i < n; i ) { int x = read(), y = read(); add(x, y); add(y, x);}dfs1(1, 0, 1);dfs2(1, 1);build(1, 1, n);for(int i = 1; i <= m; i ){int op = read();if(op == 1){int x = read(), a = read();change(x, x, a);}if(op == 2){int x = read(), a = read();updata(1, a, 1, n, pos[x], pos[x] size[x] - 1);}if(op == 3){int x = read();printf("%lld\n",asksum(x, 1));}}return 0;} 赞 (0)