5/3 树上问题

二进制：

\[\forall x\in\mathbb N^+=\sum_{i=0}^n a_i2^i \ \ \ n=O(\log x) \]

倍增：维护从每一个元素开始 \(2^i\) 个数

应用：元素和，\(k\) 级祖先等

\[u\leftarrow u\text{的}2^{a_i}\text{级祖先},\forall a_i=1 \]

---

例 \(1\): 树上 \(k\) 级祖先

记节点 \(u\) 的 \(2^i\) 级祖先为 \(f[i,u]\)，那么有 \(f[i+1,u]=f[i,f[i,u]]\)。需要注意的是，由于缓存命中问题，\(i\) 维开在外面可以提升程序效率。

时间复杂度 \(O((n+q)\log n)\)。

#include 
using namespace std;
#define rep(ii,aa,bb) for(re ll ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned int ull;
typedef double db;
typedef pair PII;
const int maxn = 5e5 + 5;
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template 
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template 
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template 
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int n, q;
ull s;
int f[25][maxn], rt = 1, dep[maxn], hd[maxn], ver[maxn * 2], nxt[maxn * 2], tot;
inline void add(int u, int v) {
	ver[++tot] = v; nxt[tot] = hd[u]; hd[u] = tot;
	ver[++tot] = u; nxt[tot] = hd[v]; hd[v] = tot;
}
inline void dfs(int u, int fa) {
	f[0][u] = fa;
	dep[u] = dep[fa] + 1;
	for(int i = 0; i < 21; i ++) 
		f[i + 1][u] = f[i][f[i][u]];
	for(int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i];
		if(v == fa) continue;
		dfs(v, u);
	}
}
inline int query(int u, int k) {
	for(int p = 20; p >= 0; p --) 
		if(k >= (1 << p)) 
			u = f[p][u], 
			k -= (1 << p);
	return u;
}
inline ull get(ull x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x; 
}
int main () {
	read(n); read(q); read(s);
	rep(i, 1, n) {
		int u;
		read(u);
		if(!u) rt = i;
		else add(u, i);
	}
//	writeln(rt);
	dfs(rt, 0);
	int ans = 0;
	ll Ans = 0;
//	rep(i, 1, n) writeln(dep[i]);
	rep(i, 1, q) {
//		int x, k;
//		read(x), read(k);
		int x = (get(s) ^ ans) % n + 1;
		int k = (get(s) ^ ans) % dep[x];
//		write(x), putchar(' '), writeln(k);
		ans = query(x, k);
//		writeln(ans);
		Ans ^= (1ll * ans * i);
	}
	writeln(Ans);
	return 0;
}

---

例 \(2\) [JLOI2014]松鼠的新家

维护 \(tag_u\) 表示 \(u\) 到根节点的路径上点权增加量。

对于一次 \(\delta(u,v)\) 的修改，只需要令 \(tag_u, tag_v+1\)，并且 \(tag_{\text{lca}(u,v)}, tag_{fa(\text{lca}(u,v))}-1\) 即可。

所有修改完成后，进行一次全局 dfs，dfs过程中维护全局量 \(s\)，表示当前节点 \(u\) 的子树对 \(u~root\) 的贡献，记

\[w_u=s_{now}=\sum_{v\in subtree(u)}tag_v \]

更方便地，我们将 \(tag[u]\) 当成前缀和式变量，即每次 dfs 后 tag[u]+=tag[v];

---

例 \(3\) 生活在树上

\(\delta(u,x),\delta(u,y)\) 总是先经过若干个节点，然后与 \(\delta(x,y)\) 所形成地链有一个交点 \(t\)。

\(dis(u,x)=dis(u,y)等价于dis(x,t)=dis(y,t)\)，因此转化为 \(\delta(x,y)\) 上寻找一个点 \(t\) 满足。

推出 \(dis(x,y)\oplus w_t=0,dis(x,y)=w_t\)

对询问差分：查询链上满足点地个数。\(dis\) 可以使用树上前缀和，\(dis(x,y)=dis[x]\oplus dis[y]\oplus w_{lca}\)