完全不需要剖分啊,不知道 tag 在打什么劲。
首先看题面。
操作1是正常的操作,开一颗线段树记录 dfs 序区间修改。
操作2是反常的操作。这题需要记 bfs 序。这样就可以确保一个节点的直连节点 bfs 序是连续的。然后再开一颗线段树记录 bfs 序区间修改。
注意哦,一个节点和他的子节点的 bfs 序不一定是连续的,所以 bfs 预处理的时候对于每个节点要处理出他 bfs 序最小的孩子,也就是第一个访问到的孩子。
然后你再手动增加 \(a\) 数组中节点父亲和自身的值就行。
这样对于最后的查询,每个节点就是第一棵线段树的值 + 第二棵线段树的值 + \(a\) 的值。
发现两个操作都是要求区间修改 + 单点查询,那可以不写线段树了,改成树状数组。(其实线段树的大常数也过不去)
呃然后就没啥说的了(存疑
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define int long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 1e6 + 6;
bool vis[N];
int m, opt, n, u, v, cnt, tot, a[N], bfn[N], dfn[N], con[N], siz[N], son[N], father[N];
vector<int> e[N];
void bfs() {queue<int> q;q.push(1);vis[1] = 1;while(!q.empty()) {int now = q.front();q.pop();bfn[now] = ++cnt;//处理bfs序for(const register int to : e[now]) {if(!vis[to]) {q.push(to);vis[to] = 1;if(!son[now]) {son[now] = to//为了后续的修改,记录bfs序最小的儿子}++con[now];//和siz一个性质}} }
}
void dfs(int s, int fa) {father[s] = fa;dfn[s] = ++tot;siz[s] = 1;for(const register int to : e[s]) {if(to == fa) continue;dfs(to, s);siz[s] += siz[to];}
}
struct BIT {int sum[N];inline void add(int x, int d) {while(x <= n) {sum[x] += d;x += lowbit(x);}}inline void Add(int l, int r, int d) {add(l, d);add(r + 1, -d);}inline int query(int x) {int ans = 0;while(x) {ans += sum[x];x -= lowbit(x);}return ans;}
//就是一个支持区间加单点查的树状数组
}T1, T2;
signed main() {ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;rep(i, 1, n) cin >> a[i];rep(i, 1, n - 1) {cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}bfs();dfs(1, 0);cin >> m;while(m--) {cin >> opt >> u >> v;;switch(opt) {case 1 : {T1.Add(dfn[u], dfn[u] + siz[u] - 1, v);//改子树break;}case 2 : {a[father[u]] += v;//改父亲a[u] += v;//改自己if(son[u]) {T2.Add(bfn[son[u]], bfn[son[u]] + con[u] - 1, v);//改儿子}break;}}}cin >> m;while(m--) {cin >> opt;cout << T1.query(dfn[opt]) + T2.query(bfn[opt]) + a[opt] << '\n';}return 0;
}