SDOI2017切树游戏——树上动态DP、FWT

%%%imortalCO

题目描述!

有一个n个结点的树，每个节点有权值v，有以下操作：

• Change x y，将编号为 x的结点的权值修改为 y。
• Query k，询问有多少棵 T 的非空连通子树，满足其价值恰好为 k。

数据规模 n,m <= 30000,v <= 128且m为2的幂次

算法讨论

考虑没有修改操作, 我们可以定以下状态

$$f[i][k]表示以i为根，异或值为k的答案$$

转移的时候就是一个背包

$$当前讨论到子树u ：f[i][k] += \sum_{j = 0}^{128}f[u][j]*f[i][k\ xor\ j]$$

直接处理是$O(n128^2)$ 的，利用$FWT$优化，预先求出所有数组的点值表示，最后$FWT$回来，可以做到$O((n+log128)*128)$

那么对于原问题，也可使用。。

额这个我写不下去了。。我发现我想写的跟ImmortalCO大佬的一模一样。。还是去看大佬写的吧

代码：

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 30005, REV = 5004, M = 129, mod = 10007;

char buf[1 << 20], *p1, *p2;
#ifndef GC
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
#endif
inline int _R() {
	int d = 0; char t; bool ty = 1;
	while (t = GC, (t < '0' || t > '9') && t != '-') ;
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}
inline void _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
}


int n, m, q;
struct Data {
	int a[M];
	void FWT(int ty) {
		for (int w = 1; w < m; w <<= 1)
			for (int k = 0; k < m; k += w << 1)
				for (int i = k; i < k + w; i ++) {
					int f = a[i], g = a[i + w];
					if (ty == 1) a[i] = (f + g) % mod, a[i + w] = (f - g + mod) % mod;
					else a[i] = (f + g) * REV % mod, a[i + w] = (f - g + mod) * REV % mod;
				}
	}

	void set(int d) {
		for (int i = 0; i < m; i ++) a[i] = d;
	}
	void Init(int x) {
		set(0);
		a[x] = 1, FWT(1);
	}
	Data increase() const {
		Data ret;
		for (int i = 0; i < m; i ++) ret.a[i] = (a[i] + 1) % mod;
		return ret;
	}
	Data operator + (const Data& rhs) const {
		Data rt;
		for (int i = 0; i < m; i ++) rt.a[i] = (a[i] + rhs.a[i]) % mod;
		return rt;
	}
	Data operator * (const Data& rhs) const {
		Data rt;
		for (int i = 0; i < m; i ++) rt.a[i] = a[i] * rhs.a[i] % mod;
		return rt;
	}
} A[N], null;

struct tr_matrix;
struct sb_data;

struct sb_data {
	Data f, h;
	sb_data operator + (const sb_data& rhs) const {
		return (sb_data) {f * rhs.f, h + rhs.h};
	}
	void Init() { f.set(1); }
	tr_matrix to_tr_matrix() const;
} ;

struct tr_matrix {
	Data a, b, c, d;
	tr_matrix operator * (const tr_matrix& rhs) const {
		return (tr_matrix) {a * rhs.a, 
							a * rhs.b + b, 
							c * rhs.a + rhs.c, 
							c * rhs.b + d + rhs.d};
	}
	void Init() { a.set(1); }
	sb_data to_sb_data() const;
};

tr_matrix sb_data :: to_tr_matrix() const { return (tr_matrix) {f, f, f, f + h}; }
sb_data tr_matrix :: to_sb_data() const { return (sb_data) {b.increase(), d}; }


namespace Point {
	struct Node {
		Node *Son[2];
		sb_data val;
	} pool[N * 5], *root[N], *tl, *null;
	void Init() {
		tl = null = pool;
		null -> val.Init();
		for (int i = 1; i <= n; i ++) root[i] = null;
	}
	void update(Node* x) {
		x -> val = x -> Son[0] -> val + x -> Son[1] -> val;
	}
	void Modify(Node *&p, int l, int r, int k, const sb_data& x) {
		if (p == null) p = ++ tl, p -> Son[0] = p -> Son[1] = null;
		if (l == r) { p -> val = x; return; }
		int mid = l + r >> 1;
		(k <= mid) ? Modify(p -> Son[0], l, mid, k, x) : Modify(p -> Son[1], mid + 1, r, k, x);
		update(p);
	}
}

namespace Chain {
	struct Node {
		Node *Son[2];
		tr_matrix val;
	} pool[N * 5], *root[N], *tl, *null;
	void Init() {
		tl = null = pool;
		null -> val.Init();
		for (int i = 0; i <= n; i ++) root[i] = null;
	}
	void update(Node* x) {
		x -> val = x -> Son[0] -> val * x -> Son[1] -> val;
	}
	void Modify(Node *&p, int l, int r, int k, const tr_matrix& x) {
		if (p == null) p = ++ tl, p -> Son[0] = p -> Son[1] = null;
		if (l == r) { p -> val = x; return; }
		int mid = l + r >> 1;
		(k <= mid) ? Modify(p -> Son[0], l, mid, k, x) : Modify(p -> Son[1], mid + 1, r, k, x);
		update(p);
	}
}


int Tote, Last[N], Next[N << 1], End[N << 1];
#ifndef ADDE
#define ADDE(ST, END) (End[++ Tote] = END, Next[Tote] = Last[ST], Last[ST] = Tote)
#endif

int Dep[N], Son[N], Bln[N], Cnt[N], Pos[N];
int Pos_ln[N], Pos_ch[N], Len[N], cntc;

int dfs1(int x, int fa) {
	Dep[x] = Dep[fa] + 1;
	int i, u, tmp, sz = 1, maxx = 0;
	Cnt[x] = 1;
	for (i = Last[x]; i; i = Next[i])
		if ((u = End[i]) != fa)
			if (tmp = dfs1(u, x), sz += tmp, Cnt[x] ++, tmp > maxx)
				maxx = tmp, Son[x] = u;
	return sz;
}

void dfs2(int x, int fa, int tp) {
	Pos[x] = Dep[x] - Dep[tp] + 1;
	Bln[x] = cntc;
	Len[cntc] ++;

	if (Son[x]) dfs2(Son[x], x, tp);

	int i, j, u, tmp;
	Point :: Modify(Point :: root[x], 1, Cnt[x], 1, (sb_data) {A[x], null});

	for (i = Last[x], j = 2; i; i = Next[i], j ++)
		if (u = End[i], u != fa && u != Son[x]) {
			cntc ++;
			tmp = cntc;
			Pos_ln[cntc] = x;
			Pos_ch[cntc] = j;
			dfs2(u, x, u);
			Point :: Modify(Point :: root[x], 1, Cnt[x], j, Chain :: root[tmp] -> val.to_sb_data());
		}
	Chain :: Modify(Chain :: root[Bln[x]], 1, Len[Bln[x]], Pos[x], Point :: root[x] -> val.to_tr_matrix());
}


int main () {
	int i, j, k, x, y, u, v;

	n = _R(), m = _R();

	for (i = 1; i <= n; i ++) {
		k = _R();
		A[i].Init(k);
	}

	for (i = 1; i < n; i ++) {
		x = _R(), y = _R();
		ADDE(x, y);
		ADDE(y, x);
	}

	dfs1(1, 0);
	Chain :: Init();
	Point :: Init();
	dfs2(1, 0, 1);

	q = _R();
	char opt[20];
	Data ans;
	sb_data tmp;
	bool flag = 0;

	for (i = 1; i <= q; i ++) {
		_S(opt);

		if (opt[0] == 'Q') {
			k = _R();
			if (!flag) {
				flag = 1;
				ans = Chain :: root[0] -> val.d;
				ans.FWT(0);
			}
			printf("%d\n", ans.a[k]);
		}

		else {
			x = _R(), y = _R();
			A[x].Init(y);
			Point :: Modify(Point :: root[x], 1, Cnt[x], 1, (sb_data) {A[x], null});
			Chain :: Modify(Chain :: root[Bln[x]], 1, Len[Bln[x]], Pos[x], Point :: root[x] -> val.to_tr_matrix());

			for (k = Bln[x]; k; k = v) {
				u = Pos_ln[k];
				v = Bln[u];
				Point :: Modify(Point :: root[u], 1, Cnt[u], Pos_ch[k], Chain :: root[k] -> val.to_sb_data());
				Chain :: Modify(Chain :: root[v], 1, Len[v], Pos[u], Point :: root[u] -> val.to_tr_matrix());
			}
			flag = 0;
		}

	}
}