首页 > 其他分享 >树上差分等操作

树上差分等操作

时间：2024-05-03 22:16:11浏览次数：16  
标签：const int Ans 差分 Dep MAXN LCA 操作 树上

树链剖分 & 树上差分


有一些相关的 树上操作

主要是写 可持久化 的时候的时候

发现 \(lxl ~ Day ~ 5\) 中 有些东西根本不是 可持久化...

树链剖分

主要记录 重链剖分，不讲基本原理，只是题解


CF536E Tavas on the Path

好像并没有 可持久化，但是 树剖

先考虑在 序列 上做这个问题，如果直接快进到 \(01\) 序列那一部分

那么我们 维护一个线段树 就可以做了，具体一点，我们维护以下 四个内容

区间 前缀 \(1\) 的个数 \(Pre\)，后缀 \(1\) 的个数 \(Suf\)，区间答案 \(Ans\)，区间全是 \(1\) 吗 \(Ful\)

合并 的时候需要小心 顺序不能反（显然 前后缀 这东西并 不符合交换律）

inline Node operator + (const Node &a) const {
    Node x;
    x.L = L, x.R = a.R;
    x.Ans = Ans + a.Ans - Val[Suf] - Val[a.Pre] + Val[Suf + a.Pre];
    x.Pre = Ful * a.Pre + Pre;
    x.Suf = a.Ful * Suf + a.Suf;
    x.Ful = Ful & a.Ful;
    return x;
}

然后查区间答案就行，回到树上

注意这道题是 边权，一般树剖维护 点权，比较难泵

考虑 一个点 只有一个父亲，也只有一个父亲下来的边

可以把 边权下放到它连接的深度较深的点的点权，注意这个 \(trick\)

注意最后 查答案的时候 要 除掉 \(LCA\)（它代表它父亲连向它的边）

然后 正常树剖，正常线段树维护，查答案就行

注意一些细节，考虑 线段树节点合并时顺序是敏感的

所以查答案时 \(Ans1, Ans2\) 要随着 \(u, v\) 换，在 ::Query 中容易理解

然后 \(Ans1, Ans2\) 分别是 \(u \to LCA\) 和 \(v \to LCA\) 的 答案

但是最终路径实际上是 \(u \to LCA \to v\) 或 \(v \to LCA \to u\)

所以需要 交换一边 的 \(Pre\) 和 \(Suf\)，在 ::Query 的末尾容易理解

最后注意不要把 \(N, M\) 混用了... 比如 点数是 \(N\)

#include <bits/stdc++.h>

const int MAXN = 100005;

using namespace std;

struct Edge {
	int to, nxt, w;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v, const int w) {
	E[++ tot] = {v, H[u], w}, H[u] = tot;
	E[++ tot] = {u, H[v], w}, H[v] = tot;
}

namespace Tree_Cut {
	int Son[MAXN], Top[MAXN], Siz[MAXN], Dfn[MAXN], Idf[MAXN];
	int F[MAXN], D[MAXN];
	int Cnt = 0;
	
	inline void DFS1 (const int x, const int f) {
		F[x] = f, D[x] = D[f] + 1, Siz[x] = 1;
		for (int i = H[x]; i; i = E[i].nxt) 
			if (E[i].to != f) {
				DFS1 (E[i].to, x), Siz[x] += Siz[E[i].to];
				if (Siz[E[i].to] > Siz[Son[x]]) Son[x] = E[i].to;
			}
	}
	
	inline void DFS2 (const int x, const int top) {
		Top[x] = top, Dfn[x] = ++ Cnt, Idf[Cnt] = x;
		if (Son[x]) DFS2 (Son[x], top);
		for (int i = H[x]; i; i = E[i].nxt)
			if (E[i].to != F[x] && E[i].to != Son[x])
				DFS2 (E[i].to, E[i].to);
	}
}

int Val[MAXN];

namespace SegTree {
	struct Node {
		int L = 0, R = 0;
		int Pre = 0, Suf = 0, Ans = 0;
		bool Ful = 0;
		
		inline Node operator + (const Node &a) const {
			Node x;
			x.L = L, x.R = a.R;
			x.Ans = Ans + a.Ans - Val[Suf] - Val[a.Pre] + Val[Suf + a.Pre];
			x.Pre = Ful * a.Pre + Pre;
			x.Suf = a.Ful * Suf + a.Suf;
			x.Ful = Ful & a.Ful;
			return x;
		}
	} T[MAXN << 2];
	
	#define LC (x << 1)
	#define RC (x << 1 | 1)
	#define M ((T[x].L + T[x].R) >> 1)
	
	inline void Maintain (const int x) {
		T[x] = T[LC] + T[RC];
	}
	
	inline void Build (const int L, const int R, const int x = 1) {
		T[x].L = L, T[x].R = R;
		if (L == R) return ;
		Build (L, M, LC), Build (M + 1, R, RC), Maintain (x);
	}
	
	inline void Modify (const int p, const int x = 1) {
		if (T[x].L == T[x].R) return T[x].Ans = Val[1], T[x].Pre = T[x].Suf = T[x].Ful = 1, void ();
		if (p <= M) Modify (p, LC);
		else Modify (p, RC);
		Maintain (x);
	}
	
	inline Node Sum (const int L, const int R, const int x = 1) {
		if (L <= T[x].L && T[x].R <= R) return T[x];
		Node Ans = {0, 0, 0, 0, 0, 1};
		if (L <= M) Ans = Sum (L, R, LC);
		if (R >  M) Ans = Ans + Sum (L, R, RC);
		return Ans;
	}
	
	#undef M
}

using namespace Tree_Cut;

inline SegTree::Node Query (int u, int v) {
	using namespace SegTree;
	Node Ans1 = {0, 0, 0, 0, 0, 1}, Ans2 = {0, 0, 0, 0, 0, 1};
	
	while (Top[u] != Top[v]) {
		if (D[Top[u]] < D[Top[v]]) swap (u, v), swap (Ans1, Ans2);
		Ans1 = Sum (Dfn[Top[u]], Dfn[u]) + Ans1, u = F[Top[u]];
	}
	if (D[u] < D[v]) swap (u, v), swap (Ans1, Ans2);
	if (Dfn[u] != Dfn[v]) Ans1 = Sum (Dfn[v] + 1, Dfn[u]) + Ans1;
	
	return swap (Ans1.Pre, Ans1.Suf), Ans1 + Ans2;
}

struct Que {
	int u, v, w, id;
	
	inline bool operator < (const Que &a) const {
		return w > a.w;
	}
} G[MAXN], Q[MAXN];

int N, M;
int u, v, w;
int Ans[MAXN];

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	
	for (int i = 1; i <  N; ++ i) 
		cin >> Val[i];
		
	for (int i = 1; i <  N; ++ i)
		cin >> G[i].u >> G[i].v >> G[i].w, Add_Edge (G[i].u, G[i].v, G[i].w);
	
	for (int i = 1; i <= M; ++ i)
		cin >> Q[i].u >> Q[i].v >> Q[i].w, Q[i].id = i;
		
	DFS1 (1, 0), DFS2 (1, 1), SegTree::Build (1, N);
	
	for (int i = 1; i < N; ++ i)
		if (D[G[i].u] > D[G[i].v]) swap (G[i].u, G[i].v);
	
	sort (Q + 1, Q + M + 1);
	sort (G + 1, G + N);
	
	for (int i = 1, Pos = 1; i <= M; ++ i) {
		while (G[Pos].w >= Q[i].w) SegTree::Modify (Dfn[G[Pos].v]), ++ Pos;
		Ans[Q[i].id] = Query (Q[i].u, Q[i].v).Ans;
	}
	
	for (int i = 1; i <= M; ++ i) cout << Ans[i] << '\n';
	
	return 0;
}

树上差分

Luogu P1600 [NOIP2016 提高组] 天天爱跑步

十分经典的一个题了

感觉老是要和去年（\(2023\)）的 天天爱打卡 名字搞混（虽然题意完全不一样

形式化题意，即 给定一棵树，每个玩家沿一条路径 用相等的速度匀速行进

相等是指 不同的人速度相等

所有同时出发，询问对于 树上每个节点，特定时刻经过的玩家有多少

既然 每个玩家是同时出发的，这个时间就显得没什么意义，考虑 时间转距离

询问变成 对于树上每个点 \(u\)，有多少起点 \(st\) 满足 \(Dis(u, st) = w_u\)

且 \(st \to ed\) 的路径中 经过 \(u\)

模拟每个玩家的过程是 行不通的，因为对于每个玩家，路径长至多为 \(N\)

而这路径上 任意两点的 \(w\) 可能均不同

也就是 贡献给路径上的任意两点 所需的条件可能都不一样，不便 区间操作

于是我们还是考虑 从树上的点，即 “观察员” 下手，考虑 有多少玩家给他贡献

容易发现（

一条路径 \(u \to v\) 对 \(x\) 有贡献，当且仅当 \(u, v\) 中 有且仅有一个点 在 \(x\) 的 子树 内

\(u, v\) 与 \(x\) 共点的情况另行考虑

且 \(Dis (u, x) = w_x\)

但是修改一整条路径是 困难的，可以分成 \(u \to LCA\) 与 \(LCA \to v\) 两段考虑

我们建立 两个桶，实时更新 特定深度的点 个数

对于 \(u \to LCA\)，遍历到 \(u\) 时，第一桶中 \(u\) 的深度 \(+ 1\)，到 \(LCA\) 时，桶中 \(u\) 的深度 \(-1\)

对于 \(LCA \to v\)，遍历到 \(v\) 时，第二桶中 \(Dis(u, v) - Dep_v\) \(+1\)，到 \(LCA\) 父亲 时 \(-1\)

注意到这里通过 一次在 \(LCA\) 减，一次在 \(fa_{LCA}\) 减 的方式，使 \(LCA\) 只算了一次

这样贡献就正确了

然后为什么 \(LCA \to v\) 这段的 贡献如此奇特？

注意到由于 时间是从起点 \(u\) 开始记的，于是实际上要求的始终是 \(Dis (x, u) = w_x\)

但是我们现在如果只知道 \(v\) 咋办呢？就需要转化一下了

注意到对于一个玩家 \(u \to v\)，我们容易求出 \(Dis (u, v) = Dep_u + Dep_v - 2 Dep_{LCA}\)

又有 \(Dis(u, x) = Dep_u + Dep_x - 2 Dep_{LCA} = w_x\)

于是 \(Dep_v = Dis(u, v) - w_x + Dep_x\)，于是 \(w_x - Dep_x = Dis (u, v) - Dep_v\)

所以每次 插入的是 \(Dis (u, v) - Dep_v\)

我们 \(DFS\) 整棵树

当 进入一个点 \(x\) 时，记录 第一桶在 \(Dep_x + w_x\) 深度的值，第二桶在 \(w_x - Dep_x\) 深度的值

当 退出这个点 \(x\) 时，查询 第一桶在 \(Dep_x + w_x\) 深度的值，第二桶在 \(w_x - Dep_x\) 深度的值

两次的值 做差，就得到 这个点子树内符合条件的点 个数了

在 \(Dep_x + w_x\) 处查询是 容易理解的，显然这样查出来的起点 \(u\) 满足 \(Dis(u, x) = w_x\)

那为什么在 第二个桶的 \(w_x - Dep_x\) 处 查呢？

通过上面我们推的式子 \(w_x - Dep_x = Dis (u, v) - Dep_v\) 就容易理解了

注意到 \(w_x - Dep_x\) 是有可能 为负数 的，可以通过 每次下标加上一个值 解决

也可以像 下面给出的代码 一样，建立指针指向数组中间 即可（这很好用）

实现还比较简单，一遍过了

#include <bits/stdc++.h>

const int MAXN = 300005;
const int LOGN = 20;

using namespace std;

int N, M;

struct Edge {
	int to, nxt;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v) {
	E[++ tot] = {v, H[u]}, H[u] = tot;
	E[++ tot] = {u, H[v]}, H[v] = tot;
}

int F[MAXN][LOGN], D[MAXN], LOG[MAXN];
int W[MAXN];

namespace BINLCA {
	
	bool Init = 0;
	
	inline void DFS (const int x, const int f) {
		F[x][0] = f, D[x] = D[f] + 1;
		for (int i = 1; i < LOGN; ++ i) F[x][i] = F[F[x][i - 1]][i - 1];
		for (int i = H[x]; i; i = E[i].nxt)
			if (E[i].to != f) DFS (E[i].to, x);
		
	}
	
	inline int LCA (int u, int v) {
		if (!Init) {
			DFS (1, 0), Init = 1;
			for (int i = 2; i <= N; ++ i) LOG[i] = LOG[i >> 1] + 1;
		}
		if (D[u] < D[v]) swap (u, v);
		while (D[u] > D[v]) u = F[u][LOG[D[u] - D[v]]];
		if (u == v) return u;
		for (int i = LOGN - 1; i >= 0; -- i)
			if (F[u][i] != F[v][i])
				u = F[u][i], v = F[v][i];
		return F[u][0];
	}
	
	#define LCA BINLCA::LCA
}

int Ans[MAXN], buk[MAXN << 2];
int * Buk1 = buk, * Buk2 = buk + (MAXN << 1);

struct Node {
	int Dep, Val;
};

vector <Node> Opt1[MAXN], Opt2[MAXN];

inline void DFS (const int x, const int f) {
	int Tmp = Buk1[D[x] + W[x]] + Buk2[W[x] - D[x]];
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) DFS (E[i].to, x);
	for (int i = 0; i < (int) Opt1[x].size (); ++ i) Buk1[Opt1[x][i].Dep] += Opt1[x][i].Val ;
	for (int i = 0; i < (int) Opt2[x].size (); ++ i) Buk2[Opt2[x][i].Dep] += Opt2[x][i].Val;
	int Aft = Buk1[D[x] + W[x]] + Buk2[W[x] - D[x]];
	Ans[x] += Aft - Tmp;
}

int Dis, u, v, l, f;

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	
	for (int i = 2; i <= N; ++ i) cin >> u >> v, Add_Edge (u, v);
	
	for (int i = 1; i <= N; ++ i) cin >> W[i];
	
	for (int i = 1; i <= M; ++ i) {
		cin >> u >> v;
		l = LCA (u, v), f = F[l][0], Dis = D[u] + D[v] - (D[l] << 1);
		Opt1[u].push_back ({D[u], + 1});
		Opt1[l].push_back ({D[u], - 1});
		Opt2[v].push_back ({Dis - D[v], + 1});
		Opt2[f].push_back ({Dis - D[v], - 1});
	}
	
	DFS (1, 0);
	
	for (int i = 1; i <= N; ++ i) cout << Ans[i] << ' ';
	
	return 0;
}

Luogu P2680 [NOIP2015 提高组] 运输计划

一开始还理解错题意了...

大致来讲，给定一棵 带权的树 和 一些路径

现在可以 把树上一条边边权变成 \(0\)，求 最长路径的最小长度

考虑 最值转存在，即 二分答案

我们二分这个最小长度 \(len\)，现在只需要思考 怎么判定答案的合法性

显然，对于 所有原始长度大于 \(len\) 的路径，我们需要在上面 删去一条边

最终使得 所有路径长度均小于 \(len\) 即可，反之则 \(len\) 无法取到

于是，我们可以 预处理出所有路径的原始长度，这里需要求 \(LCA\)

\(DFS\) 得到 深度，然后 \(Dep_u + Dep_v - 2 Dep_{LCA}\) 即可 \(O(1)\) 求得

对其排序，每次二分到 \(len\) 时，我们需要取出所有 大于 \(len\) 的 路径

显然 删边不会使路径变长，故 已经小于 \(len\) 的路径 均无需考虑

可以想到求出它们 边覆盖的并集，找到 被 所有路径 覆盖的 最长边

若有 任一路径没有覆盖这条边，那么 删去这条边 后

那条路径 长度不变，仍然大于 \(len\)，那么这样的删边 是不优的

找的过程就可以考虑 树上差分，遍历路径 \(u_i \to v _i\)

在 \(u_i, v_i\) 处 打上 加入标记，在 \(LCA\) 处打上 两个删除标记

运用 边下放到点 的 \(trick\)（树上每个结点 到父亲的边是唯一的）

于是 \(DFS\) 这棵树，先 遍历每个点的儿子，求和儿子的贡献

然后加上 这个点的标记，就得到了这个点（对应边）被 经过的次数

于是 \(O (N)\) 遍历一遍边 就能找到 被 所有路径 覆盖的 最长边 了

显然我们再找到 最长路径（即从大到小排序后的第一条路径）

若 最长路径长减去这个最长边 小于等于 \(len\)，则 \(len\) 可被取到

反之增大 \(len\) 再判断即可，时间复杂度 \(O(N \log N)\)

又是一个 好写好调 的题，注意 差分时先遍历儿子再加自身 即可

#include <bits/stdc++.h>

const int MAXN = 300005;
const int LOGN = 20;

using namespace std;

struct Edge {
	int to, nxt, w;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v, const int w) {
	E[++ tot] = {v, H[u], w}, H[u] = tot;
	E[++ tot] = {u, H[v], w}, H[v] = tot;
}

int F[MAXN][LOGN], D[MAXN], LOG[MAXN];
int N, M;

namespace BINLCA {
	
	bool Init = 0;
	
	inline void DFS (const int x, const int f) {
		F[x][0] = f, D[x] = D[f] + 1;
		for (int i = 1; i < LOGN; ++ i) F[x][i] = F[F[x][i - 1]][i - 1];
		for (int i = H[x]; i; i = E[i].nxt)
			if (E[i].to != f) DFS (E[i].to, x);
	}
	
	inline int LCA (int u, int v) {
		if (!Init) {
			for (int i = 2; i <= N; ++ i) LOG[i] = LOG[i >> 1] + 1;
			DFS (1, 0), Init = 1;
		}
		if (D[u] < D[v]) swap (u, v);
		while (D[u] > D[v]) u = F[u][LOG[D[u] - D[v]]];
		if (u == v) return u;
		for (int i = LOGN - 1; i >= 0; -- i)
			if (F[u][i] != F[v][i])
				u = F[u][i], v = F[v][i];
		return F[u][0];
	}
}

struct Path {
	int u, v, l, d;
	
	inline bool operator < (const Path &a) const {
		return d > a.d;
	}
} Q[MAXN];

int S[MAXN], P[MAXN], Dep[MAXN];

inline void DFS1 (const int x, const int f) {
	int Tmp = 0;
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) DFS1 (E[i].to, x), Tmp += P[E[i].to];
	Tmp += S[x], P[x] = Tmp;
}

inline void DFS2 (const int x, const int f) {
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) Dep[E[i].to] = Dep[x] + E[i].w, DFS2 (E[i].to, x);
}

inline bool Check (const int x) {
	memset (S, 0, sizeof S);
	memset (P, 0, sizeof P);
	
	int Max = 0, Cnt = 0;
	
	for (int i = 1; i <= M; ++ i) {
		if (Q[i].d <= x) break ;
		Cnt ++, S[Q[i].u] ++, S[Q[i].v] ++, S[Q[i].l] -= 2; 
	}
	
	DFS1 (1, 0);
	
	for (int i = 2; i <= N; ++ i)
		if (P[i] == Cnt) Max = max (Max, Dep[i] - Dep[F[i][0]]);
	
	if (Q[1].d - Max <= x) return 1;
	return 0;
}

int u, v, w, lca;

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	
	for (int i = 2; i <= N; ++ i) 
		cin >> u >> v >> w, Add_Edge (u, v, w);
	
	DFS2 (1, 0);
	
	for (int i = 1; i <= M; ++ i)
		cin >> Q[i].u >> Q[i].v, Q[i].l = BINLCA::LCA (Q[i].u, Q[i].v), Q[i].d = Dep[Q[i].u] + Dep[Q[i].v] - (Dep[Q[i].l] << 1);
	
	sort (Q + 1, Q + M + 1);
	
	int L = 0, R = Q[1].d, Mid, Ans = Q[1].d;
	
	while (R - L >= 1) {
		Mid = (L + R) >> 1;
		if (Check (Mid)) R = Ans = Mid;
		else L = Mid + 1;
	}
	
	cout << Ans << endl;
	
	return 0;
}

其他操作

\(DFS\) 序问题

CF383C Propagating tree

注意到修改 子树信息，于是想到 \(DFS\) 序，子树转序列区间

容易想到 结点深度奇偶 对修改时的权值贡献正负 有影响

考虑记录 \(DFS\) 序区间内 奇偶结点个数

同时 标记 也按 **操作中修改的那个点的深度奇偶 **分开成两个

然后正常 区间和，单点查 线段树维护 即可

注意下传标记的时候 奇偶 贡献，不要反了

#include <bits/stdc++.h>

const int MAXN = 200005;

using namespace std;

struct Edge {
	int to, nxt;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v) {
	E[++ tot] = {v, H[u]}, H[u] = tot;
	E[++ tot] = {u, H[v]}, H[v] = tot;
}

int Dfn[MAXN], Rdf[MAXN], Idf[MAXN], Dep[MAXN], Val[MAXN], Cnt = 0;

namespace SegTree {
	struct Node {
		int L, R;
		int Siz[2] = {0, 0}, Tag[2] = {0, 0};
		long long v;
	} T[MAXN << 2];
	
	#define LC (x << 1)
	#define RC (x << 1 | 1)
	#define M ((T[x].L + T[x].R) >> 1)
	
	inline void Maintain (const int x) {
		T[x].Siz[0] = T[LC].Siz[0] + T[RC].Siz[0];
		T[x].Siz[1] = T[LC].Siz[1] + T[RC].Siz[1];
		T[x].v = T[LC].v + T[RC].v;
	}
	
	inline void Update (const int x) {
		T[LC].v += 1ll * (T[LC].Siz[0] - T[LC].Siz[1]) * (T[x].Tag[0] - T[x].Tag[1]);
		T[RC].v += 1ll * (T[RC].Siz[0] - T[RC].Siz[1]) * (T[x].Tag[0] - T[x].Tag[1]);
		T[LC].Tag[0] += T[x].Tag[0];
		T[RC].Tag[0] += T[x].Tag[0];
		T[LC].Tag[1] += T[x].Tag[1];
		T[RC].Tag[1] += T[x].Tag[1];
		T[x].Tag[0] = T[x].Tag[1] = 0;
	}
	
	inline void Build (const int L, const int R, const int x = 1) {
		T[x].L = L, T[x].R = R;
		if (L == R) return T[x].v = Val[Idf[L]], T[x].Siz[Dep[Idf[L]] & 1] = 1, void ();
		Build (L, M, LC), Build (M + 1, R, RC), Maintain (x);
	}
	
	inline void Modify (const int L, const int R, const bool f, const int v, const int x = 1) {
		if (T[x].L  > R || L >  T[x].R) return ;
		if (L <= T[x].L && T[x].R <= R) return T[x].Tag[f] += v, T[x].v += v * (f ? T[x].Siz[1] - T[x].Siz[0] : T[x].Siz[0] - T[x].Siz[1]), void ();
		Update (x), Modify (L, R, f, v, LC), Modify (L, R, f, v, RC), Maintain (x);
	}
	
	inline long long Query (const int p, const int x = 1) {
		if (T[x].L == T[x].R) return T[x].v;
		Update (x);
		if (p <= M) return Query (p, LC);
		else return Query (p, RC);
	}
	
	#undef M
}

using namespace SegTree;

inline void DFS (const int x, const int f) {
	Dfn[x] = ++ Cnt, Idf[Cnt] = x, Dep[x] = Dep[f] + 1;
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) DFS (E[i].to, x);
	Rdf[x] = Cnt;
}

int N, M;

int Opt, u, v;

signed main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	
	for (int i = 1; i <= N; ++ i) cin >> Val[i];
	
	for (int i = 2; i <= N; ++ i)
		cin >> u >> v, Add_Edge (u, v);
		
	DFS (1, 0), Build (1, N);
	
	for (int i = 1; i <= M; ++ i) {
		cin >> Opt;
		if (Opt == 1) cin >> u >> v, Modify (Dfn[u], Rdf[u], Dep[u] & 1, v);
		if (Opt == 2) cin >> u, cout << Query (Dfn[u]) << '\n';
	}
	
	return 0;
}

但实际上这样写 比较唐氏

考虑如果我们 分奇偶建立两颗线段树 就可以完全按 普通区间加 来维护了

一棵只对 深度为奇数 的结点 有效，另一棵对 深度为偶数 的结点有效

然后按照 单点修改 的 那个点深度奇偶，给两棵树分别加 正负权值

最后一想，区间和甚至 不用线段树，两个 树状数组 就解决了，又短又快

几乎没有细节，直接实现即可

#include <bits/stdc++.h>

const int MAXN = 200005;

using namespace std;

struct Edge {
	int to, nxt;
} E[MAXN << 1];

int H[MAXN], tot;

inline void Add_Edge (const int u, const int v) {
	E[++ tot] = {v, H[u]}, H[u] = tot;
	E[++ tot] = {u, H[v]}, H[v] = tot;
}

int N, M, Cnt;
int Ldf[MAXN], Rdf[MAXN], Dep[MAXN], Val[MAXN];

namespace BIT {
	int T[2][MAXN];
	
	#define lowbit(x) (x & -x)
	
	inline void add (int x, const int v, const bool f) {
		while (x <= N) T[f][x] += v, x += lowbit (x);
	}
	
	inline void Add (const int L, const int R, const int v, const bool f) {
		add (L, + v, f), add (R + 1, - v, f);
	}
	
	inline int Sum (int x, const int f) {
		int Ret = 0;
		while (x) Ret += T[f][x], x -= lowbit (x);
		return Ret;
	}
}

inline void DFS (const int x, const int f) {
	Ldf[x] = ++ Cnt, Dep[x] = Dep[f] + 1;
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f) DFS (E[i].to, x);
	Rdf[x] = Cnt;
}

int Opt, L, R;

int main () {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> M;
	
	for (int i = 1; i <= N; ++ i) cin >> Val[i];
	
	for (int i = 2; i <= N; ++ i) cin >> L >> R, Add_Edge (L, R);
	
	DFS (1, 0);
	
	for (int i = 1; i <= N; ++ i) BIT::Add (Ldf[i], Ldf[i], Val[i], 0), BIT::Add (Ldf[i], Ldf[i], Val[i], 1);
	
	for (int i = 1; i <= M; ++ i) {
		cin >> Opt;
		if (Opt == 1) {
			cin >> L >> R;
			BIT::Add (Ldf[L], Rdf[L], + R, Dep[L] % 2 == 0);
			BIT::Add (Ldf[L], Rdf[L], - R, Dep[L] % 2 == 1);
		}
		if (Opt == 2) {
			cin >> L, cout << (Dep[L] & 1 ? BIT::Sum (Ldf[L], 0) : BIT::Sum (Ldf[L], 1)) << '\n';
		}
	}
	
	return 0;
}

标签：const,int,Ans,差分,Dep,MAXN,LCA,操作,树上
From： https://www.cnblogs.com/FAKUMARER/p/18171708

相关文章

  • 操作系统
    操作系统导航目录操作系统导航一、操作系统的作用二、进程管理概念进程与程序的区别进程管理-进程状态:三态模型进程管理-进程状态:五态模型进程管理-前趋图进程管理-进程的同步与互斥进程管理-PV操作进程管理-死锁三、存储管理分区存储页式存储段式存储段页式储存虚拟储存页面......
  • 操作系统
    操作系统是计算机系统中最基本的软件之一，它负责管理和协调计算机的硬件和软件资源，为用户提供高效、稳定、安全的运行环境。操作系统的主要功能包括进程管理、内存管理、文件系统、网络通信和用户界面等。在进程管理方面，操作系统负责创建、调度和终止进程，确保进程之间的合理分配和......
  • 操作系统
    操作系统是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。操作系统的功能包括管理计算机系统的硬件、软件及数据资源，控......
  • 计算机操作系统
    计算机操作系统作为计算机系统的核心，其发展历程见证了计算机技术的飞速进步。从最早的单机操作系统到如今网络化、智能化的操作系统，计算机操作系统在功能、性能、安全性等方面都取得了显著的提升。操作系统的基本功能主要包括资源管理、程序调度、用户界面和系统维护等。为了实现......
  • 操作系统
    微机结构和操作系统是计算机科学中的两个重要概念，它们共同构成了计算机系统的核心。微机结构指的是计算机硬件的基本组成和运作方式，包括中央处理器（CPU）、内存、输入/输出设备等。而操作系统则是一种软件，负责管理和协调计算机硬件和软件资源，提供用户与计算机之间的交互界面。微机结......
  • 操作系统
    计算机操作系统就是计算机的“大脑”和“心脏”，负责管理和控制计算机的各个部分，让它们能够协调、高效地工作。如果没有它，计算机就像是一堆没有灵魂的机器，无法发挥它的最大潜力。操作系统提供了一个称为“设备管理器”的工具，用于查看和管理连接到计算机的所有设备。用户可以通过设......
  • 操作系统
    操作系统是一种内置的程序，它负责协作计算机的各种硬件，以与用户进行交互。它是计算机最基本也是最为重要的基础性系统软件。以下是关于操作系统的更多信息：种类与类型：种类：操作系统的种类很多，可以从简单到复杂，例如手机的嵌入式操作系统到超级计算机的大型操作系统。常见的操作系统......
  • 操作系统
    操作系统：管理、控制计算机软硬件资源，合理组织计算机工作流程以方便用户有效使用计算机的程序集合。操作系统的特点：1.硬件相关、应用无关2.核心常驻内存3.中断驱动4.权威性5.庞大、复杂6.重要性7.并发性（宏观并行，微观串行）、共享性（多个程序共同使用）、虚拟性、异步性操作系统的核心......
  • 操作系统
    操作系统是管理、控制计算机软硬件资源，组织计算机工作流程，以方便用户有效使用计算机的有序程序集合。操作系统拥有1.并发性（宏观并行，微观串行）：指两个或多个事件再同一时间间隔同时执行，互不干涉2.共享性：指系统的资源可以被多个程序共同使用以此提高系统的效率3.异步性：指多个程序在同......
  • 关于操作系统
    操作系统是管理计算机硬件与软件资源的系统软件，它在计算机系统中起着至关重要的作用。操作系统负责协调和管理计算机的各种任务，如进程管理、内存管理、文件系统管理、设备管理等。它为用户和应用程序提供了一个友好的操作环境，使人们能够方便地使用计算机。同时，操作系统还确保了......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99