首页 > 其他分享 >全局平衡二叉树学习笔记 && [SDOI2017]切树游戏解题报告

全局平衡二叉树学习笔记 && [SDOI2017]切树游戏解题报告

时间：2023-12-06 22:34:08浏览次数：58  
标签：rt arr fs 切树 int 二叉树 && FWT fl

首先，任何一个卡树剖的出题人都很没有素质

前言

2023 年 8 月 22 日，XDFnoip模拟赛场上，神犇 liuhangxin 自己发明了矩阵乘法维护FWT，可是出成绩的时候发现本题挂了30分。

2023 年 9 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。

2023 年 10 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。

2023 年 11 月 22 日，菜鸡 cool_milo 看到了 liuhangxin 的题解，但是由于太菜，并没有看懂。

2023 年 12 月 5 日，菜鸡 cool_milo 看到神仙 liuhangxin 讨论切树游戏那题，发现 liuhangxin 会 矩阵乘法维护FWT 而自己不会。

2023 年 12 月 6 日，菜鸡 cool_milo 最终还是学习了矩阵乘法维护FWT，并且在 300min 切掉此题。

一个月前我在 NOIp2023 的赛场上，散散沙。一个月后，我从倒下的地方爬起。

我成功了。我不再是以前的那个我了。

什么是全局平衡二叉树

顾名思义，是全局看来都很平衡的二叉树

我们参考树剖的思想，对原树进行轻重链剖分：

SSH

（图源oiwiki，下同）

我们思考树链剖分的劣势在哪里：树剖的过程和数据结构是割裂的，两个的复杂度是相乘的关系，所以就显得很没有必要。虽然 LCT 能够消除这一劣势，但是在没有Link和cut的时候就显得很多余我不想背这么多代码。

那我们可以试着魔改一下LCT，还是借用一条链一棵二叉树的方式建树，但是选择 整条链的带权重心作为根。每个点的权定义为它的 \(size\) 减去 它的重儿子的 \(size\) 。

而每一条轻边在树上体现为 二叉树的根 （注意不是轻子树的头）到重链上的一条单向边，和LCT类似，这条边满足“认父不认子”。

Karry

这样的好处是什么呢？：我们在这个“二叉树”上往父亲走一次，整个树的大小至少翻倍。因为这里每个点的 \(size\) 其实就是它管辖的那一段重链的长度加上重链的轻子树的大小之和。

感觉不太难理解吧？

先贴一个建树代码：

code 
int Sbuild(int l, int r) {
		if(l > r) return 0;
		int sum = 0;
		for(int i = l; i <= r; i++) {
			sum += lsze[stk[i]];
		}
		for(int i = l, sum2 = lsze[stk[l]]; 1; i++, sum2 += lsze[stk[i]]) {
			if(sum2 * 2 > sum) {
				int rt = stk[i];
				lc[rt] = Sbuild(l, i - 1); 
				rc[rt] = Sbuild(i + 1, r);
				if(lc[rt]) {
					fs[lc[rt]] = rt;
				}
				if(rc[rt]) {
					fs[rc[rt]] = rt;
				}
				return rt;
			} 
		}
		return -114514;
	}
	
	int Build(int u) {
		//build以u为根的重链
		for(int i = u; i; i = son[i]) {
			vis[i] = 1;
		} 
		for(int i = u; i; i = son[i]) {
			for(auto it:G[i]) {
				if(!vis[it]) {
					int rt = Build(it);
					fs[rt] = i;
				}
			}
		}
		ptr = 0;
		for(int i = u; i; i = son[i]) {
			stk[++ptr] = i;
		}
		return Sbuild(1, ptr);
	}

正题

把转移写成 \(dp\) 的形式，记 \(f_{u,k}\) 表示以 \(u\) 为根的联通块，异或得到的权值为 \(k\) 的方案数。

那么有：

\[f_{u,k} = \prod{(f_{son,i} + 0)} * {(v_u)} \]

其中乘法定义为异或卷积，'t' 定义为给数组的第 \(t\) 位加上 \(1\) （表示不选）

那么容易把所有东西全部FWT起来，然后最后再FWT回去，就能做到 dp 一次 \(\Theta(nm)\) 。

然后需要动态修改。我们先定义每个点的 \(f_{u, k}\) 为 \(F(u)\)

首先我们需要对 \(F\) 求和对吧，那么我们重新定义一个 \(S\) 表示所有 \(u\) 子树内的 \(F\) 求和。这个是容易的。

然后我们需要把 dp 写成和重儿子有关的形式：我们记 \(Fl(u)\) 表示

\[\prod (F_{v \in son_u \land v \neq wson_u} + 0) * {(v_u)} \]

记 \(Su(u)\) 表示

\[\sum S_{v \in son_u \land v \neq wson_u} \]

这里 \(*\) 表示 FWT 乘法，注意这里所有的东西都被FWT了。

那么有

\[F_u = Fl_u * (F_{wson_u} + 0) = Fl_u + Fl_u * F_{wson_u} \\ S_u = Su_u + S_{son_u} + F_u = Su_u + S_{son_u} + Fl_u * F_{wson_u} + Fl_u \]

写成矩阵形式：

\[\begin{bmatrix} Fl_u & 0 & Fl_u\\ Fl_u & 1 & Su_u + S_{son_u} + Fl_u\\ 0 & 0 & 1 \end{bmatrix} * \begin{bmatrix} F_{wson} \\ S_{wson} \\ 1 \end{bmatrix} = \begin{bmatrix} F_{u} \\ S_{u} \\ 1 \end{bmatrix} \]

注意到：

\[\begin{bmatrix} a_1 & 0 & b_1\\ c_1 & 1 & d_1\\ 0 & 0 & 1 \end{bmatrix} * \begin{bmatrix} a_2 & 0 & b_2\\ c_2 & 1 & d_2\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} a_1a_2 & 0 & a_1b_2 + b_1\\ a_2c_1 + c_2 & 1 & c_1b_2 + d_1 + d_2\\ 0 & 0 & 1 \end{bmatrix} \]

那么我们只用维护四个FWT就行了，不需要写显示的矩阵乘法。

然后就完了。。。吗？

注意到撤销一个点的贡献的时候可能要除以0，所以\(Fl\) 需要维护成 \(a * 0^y\) 的形式，写的时候恶心++。

这下是真没了。

EOF.

code(7.3k) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 10007;
const int N = 3e4+5, M = 128;
template<typename T>inline void read(T &a)
{
	a = 0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if(c == '-')	f = -1;
		c = getchar();
	}
	while(isdigit(c))
		a = a * 10 + c - 48,c = getchar();
	a *= f;
}

template<typename T,typename ...L> inline void read(T &a,L &...l)
{
	read(a),read(l...);
}
int inv[P];

typedef pair<int, int> pii;

inline pii Mul(pii A, pii B) {
	return make_pair(A.first * B.first % P, A.second + B.second);
}

inline pii Div(pii A, pii B) {
	return make_pair(A.first * inv[B.first] % P, A.second - B.second); 
} 

inline int Add(int a, int b) {
	return a + b >= P ? a + b - P : a + b;
}

inline int Mul(int a, int b) {
	return a * b % P;
}

inline void Inc(int &a, int b) {
	a = Add(a, b);
}

inline int Sub(int a, int b) {
	return a - b < 0 ? a - b + P : a - b;
}

inline int qmi(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) {
			ans = Mul(ans, a);
		}
		a = Mul(a, a);
		b >>= 1;
	}
	return ans;
}
struct FWT {
	int arr[M];
	FWT() {
		memset(arr, 0, sizeof arr);
	}
	FWT(int _k) {//kpos -> 1
		memset(arr, 0, sizeof arr);
		for(int i = 0; i < M; i++) {
			if(__builtin_parity(i & _k)) {
				arr[i] = P - 1;
			}
			else {
				arr[i] = 1;
			}
		}
	}
	FWT operator + (const FWT &A) const {
		FWT ans;
		for(int i = 0; i < M; i++) {
			ans.arr[i] = Add(arr[i], A.arr[i]);
		}
		return ans;
	}
	FWT operator * (const FWT &A) const {
		FWT ans;
		for(int i = 0; i < M; i++) {
			ans.arr[i] = Mul(arr[i], A.arr[i]);
		}
		return ans;
	}
	FWT operator - (const FWT &A) const {
		FWT ans;
		for(int i = 0; i < M; i++) {
			ans.arr[i] = Sub(arr[i], A.arr[i]);
		}
		return ans;
	}
};

FWT fwt(FWT A, int op) {
	for(int i = 1; i < M; i <<= 1) {//步长
		for(int j = 0; j < M; j += (i << 1)) {
			for(int k = 0; k < i; k++) {
				int x = A.arr[j + k], y = A.arr[i + j + k];
				A.arr[j + k] = Mul(Add(x, y), op);
				A.arr[i + j + k] = Mul(Sub(x, y), op); 
			}
		} 
	}
	return A;
}

struct Matr {
	FWT a, b, c, d;
	Matr(FWT _a = FWT(), FWT _b = FWT(), FWT _c = FWT(), FWT _d = FWT()) {
		a = _a, b = _b, c = _c, d = _d;
	}
	Matr operator * (const Matr &A) const{
		return Matr(a * A.a, b + a * A.b, A.a * c + A.c, A.b * c + d + A.d);
	}
};

vector<int> G[N];

int v[N], x, y, n, m, q;
char op[10];

namespace GlbBST {
	FWT fl[N], Su[N];
	Matr F[N], Fv[N];//F是乘积，Fv是单点的值
	pii _0fl[N][M]; 
	int son[N], sze[N], lc[N], rc[N], fs[N];//fs是GlbBst上的父亲
	int stk[N], ptr, vis[N], lsze[N]; 
	void DFS1(int u, int f) {
		sze[u] = 1;
		for(auto it:G[u]) {
			if(it != f) {
				DFS1(it, u);
				sze[u] += sze[it];
				if(sze[it] > sze[son[u]]) {
					son[u] = it;
				}
			}
		}
		lsze[u] = sze[u] - sze[son[u]];
	}
	
	int Sbuild(int l, int r) {
		if(l > r) return 0;
		int sum = 0;
		for(int i = l; i <= r; i++) {
			sum += lsze[stk[i]];
		}
		for(int i = l, sum2 = lsze[stk[l]]; 1; i++, sum2 += lsze[stk[i]]) {
			if(sum2 * 2 > sum) {
				int rt = stk[i];
				lc[rt] = Sbuild(l, i - 1); 
				rc[rt] = Sbuild(i + 1, r);
				F[rt] = Fv[rt];
				if(lc[rt]) {
					F[rt] = F[lc[rt]] * F[rt];
					fs[lc[rt]] = rt;
				}
				if(rc[rt]) {
					F[rt] = F[rt] * F[rc[rt]];
					fs[rc[rt]] = rt;
				}
				return rt;
			} 
		}
		return -114514;
	}
	
	int Build(int u) {
		//build以u为根的重链
		for(int i = u; i; i = son[i]) {
			vis[i] = 1;
			fl[i] = FWT(v[i]); 
			for(int j = 0; j < M; j++) {
				_0fl[i][j] = make_pair(fl[i].arr[j], 0);//必然非0 
			}
		} 
		for(int i = u; i; i = son[i]) {
			for(auto it:G[i]) {
				if(!vis[it]) {
					int rt = Build(it);
					fs[rt] = i;
					Su[i] = Su[i] + F[rt].d;
					FWT tmp = F[rt].b + FWT(0);
					fl[i] = fl[i] * tmp;
					for(int j = 0; j < M; j++) {
						pii res;
						if(tmp.arr[j]) {
							res = make_pair(tmp.arr[j], 0);
						} 
						else {
							res = make_pair(1, 1);
						}
						_0fl[i][j] = Mul(_0fl[i][j], res);
					}
				}
			}
		}
		ptr = 0;
		for(int i = u; i; i = son[i]) {
			Fv[i] = Matr(fl[i], fl[i], fl[i], fl[i] + Su[i]);
			stk[++ptr] = i;
		}
		return Sbuild(1, ptr);
	}
	
	void modify(int x, int y) {
		//x -> y;
		int xx = x;
		while(x) {
			if(fs[x] && lc[fs[x]] != x && rc[fs[x]] != x) {
				Su[fs[x]] = Su[fs[x]] - F[x].d;
				FWT tmp = F[x].b + FWT(0);
				for(int j = 0; j < M; j++) {
					pii res;
					if(tmp.arr[j]) {
						res = make_pair(tmp.arr[j], 0);
					}
					else {
						res = make_pair(1, 1);
					}
					_0fl[fs[x]][j] = Div(_0fl[fs[x]][j], res);
					if(_0fl[fs[x]][j].second) {
						fl[fs[x]].arr[j] = 0;
					}
					else {
						fl[fs[x]].arr[j] = _0fl[fs[x]][j].first;
					}
				} 
			}
			x = fs[x];
		}
		x = xx;
		//撤回一个贡献 
		FWT ord = FWT(v[x]);
		for(int j = 0; j < M; j++) {
			if(ord.arr[j]) {
				_0fl[x][j] = Div(_0fl[x][j], make_pair(ord.arr[j], 0));
			}
			else {
				_0fl[x][j].second--;
			}
		}
		v[x] = y;
		ord = FWT(v[x]);
		for(int j = 0; j < M; j++) {
			if(ord.arr[j]) {
				_0fl[x][j] = Mul(_0fl[x][j], make_pair(ord.arr[j], 0));
			}
			else {
				_0fl[x][j].second++;
			}
			if(_0fl[x][j].second) {
				fl[x].arr[j] = 0;
			}
			else {
				fl[x].arr[j] = _0fl[x][j].first;
			}
		}
		Fv[x] = Matr(fl[x], fl[x], fl[x], fl[x] + Su[x]);
		while(x) {
			F[x] = Fv[x];
			if(lc[x]) {
				F[x] = F[lc[x]] * F[x];
			} 
			if(rc[x]) {
				F[x] = F[x] * F[rc[x]];
			}
			if(fs[x] && lc[fs[x]] != x && rc[fs[x]] != x) {
				//修改父节点的矩阵 
				Su[fs[x]] = Su[fs[x]] + F[x].d;
				FWT tmp = F[x].b + FWT(0);
				for(int j = 0; j < M; j++) {
					pii res;
					if(tmp.arr[j]) {
						res = make_pair(tmp.arr[j], 0);
					} 
					else {
						res = make_pair(1, 1);
					}
					_0fl[fs[x]][j] = Mul(_0fl[fs[x]][j], res);
					if(_0fl[fs[x]][j].second) {
						fl[fs[x]].arr[j] = 0;
					}
					else {
						fl[fs[x]].arr[j] = _0fl[fs[x]][j].first;
					}
				}
				Fv[fs[x]] = Matr(fl[fs[x]], fl[fs[x]], fl[fs[x]], fl[fs[x]] + Su[fs[x]]); 
			}
			x = fs[x];
		} 
	}
}

int main() {
	//freopen("1.in", "r", stdin);
	for(int i = 1; i < P; i++) {
		inv[i] = qmi(i, P - 2);
	}
	read(n, m);
	for(int i = 1; i <= n; i++) {
		read(v[i]);
	}
	for(int i = 1; i < n; i++) {
		read(x, y);
		G[x].emplace_back(y), G[y].emplace_back(x); 
	}
	read(q);
	GlbBST::DFS1(1, 0);
	int root = GlbBST::Build(1);
//	for(int i = 1; i <= n; i++) {
//		cout<<i<<' '<<GlbBST::fs[i]<<endl;
//	}
	while(q--) {
		scanf("%s", op);
		if(op[0] == 'C') {
			read(x, y);
			GlbBST::modify(x, y);
		} 
		else {
			read(x);
			FWT res = fwt(GlbBST::F[root].d, (P + 1) >> 1);
			printf("%d\n", res.arr[x]);
		}
	}
}



//FWT是好东西——Sword_K

/*
[a1 0 b1]    [a2 0 b2]     [a1a2       0    b1+a1b2]
[c1 1 d1] *  [c2 1 d2]  =  [a2c1+c2    1 b2c1+d1+d2]
[0  0  1]    [0  0  1]     [0          0          1]
*/ 


/*
	start coding at:2023/12/6 10:32
	finish debugging at:2023/12/6 15:14
	stubid mistakes:枚举重儿子写出死循环，树剖it = f没有continue，传参传挂，轻子树的父亲设为自己，所有的FWT(0)都应该是FWT(1)，FWT一个数的结果不是1和0，撤销贡献的时候Su[fs[x]]写成Su[x] 
*/

/*
  吾日三省吾身：
  你排序了吗？
  你取模了吗？
  你用%lld输出long long 了吗？
  1LL<<x写对了吗？
  判断=0用了abs()吗？
  算组合数判了a<b吗？
  线段树build()了吗？
  .size()加了(signed)吗？
  树链剖分的DFS序是在第二次更新的吗？
  修改在询问前面吗？
  线段树合并到叶子结点return了吗？
  __builtin_ctz后面需要加ll吗？
*/

标签：rt,arr,fs,切树,int,二叉树,&&,FWT,fl
From： https://www.cnblogs.com/miloHogwarts4ever/p/orz-Invisible-liuhangxin.html

相关文章

  • 2.二叉树层序遍历
    107.二叉树的层序遍历II相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。classSolution{//利用链表可以进行o(1)头部插入publicLinkedList<List<Integer>>res=newLinkedList<List<Integer>>();publicList<List<Integer>>levelOrd......
  • 1.二叉树
    二叉树的种类满二叉树满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。完全二叉树完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边......
  • 第5章. 二叉树
    二叉树一、树的基本概念节点、根节点、父节点、子节点、兄弟节点一棵树可以没有任何节点，称为空树一棵树可以只有一个节点，也就是只有根节点子树、左子树、右子树节点的度：子树的个数树的度：所有节点度中的最大值叶子节点：度为0的节点非叶子节点：度不为0的节点层数：根节点......
  • 17_二叉树的所有路径
    二叉树的所有路径给你一个二叉树的根节点root，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例1：输入：root=[1,2,3,null,5]输出：["1->2->5","1->3"]示例2：输入：root=[1]输出：["1"]【思路】题目要求从根节点到叶子的路径，所以需要......
  • 16_平衡二叉树
    平衡二叉树【题外话】二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（从上往下看）二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。（从下往上看）小疑惑：为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。（本质上求解的就是根节......
  • 15_完全二叉树的节点个数
    完全二叉树的节点个数给你一棵完全二叉树的根节点root，求出该树的节点个数。完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层，则该层包含1~2h个节点。示......
  • 二叉树创建及遍历
    #include<stdio.h>#include<iostream>usingnamespacestd;typedefcharTElemType;typedefvoidStatus;typedefintElemType;typedefstructBiTNode{ TElemTypedata; BiTNode*lchild,*rchild;}BiTNode,*BiTree;voidCreateBiTree(BiTree......
  • C++U5-08-二叉树1
    上节课作业分析讲解视频链接：https://pan.baidu.com/s/1_jaM_TlZmLJX4JbLuJtKzA?pwd=2us4提取码：2us4学习目标  树在C++中，二叉树是一种常用的数据结构，由节点（Node）组成，每个节点可以有最多两个子节点。二叉树具有以下几个主要的作用：存储和组织数据：二叉树可用于存储和组织大......
  • 二叉树
    二叉树分析二叉树的前序，中序，后序的遍历步骤1.创建一颗二叉树2前序遍历2.1先输出当前节点初始的时候是root节点2.2如果左子节点不为空则递归继续前序遍历2.3如果右子节点不为空，则递归继续前序遍历3.中序遍历3.1如果当前节点的左子节点不为空,则递归中序遍历3.2输出当前......
  • 多叉树转二叉树
    CPP代码点击查看代码#include<iostream>#include<queue>#include<stack>usingnamespacestd;//多叉树节点structNode{ stringname;//节点名称 vector<Node*>nodes;//子节点指针数组 // 构造函数 Node(stringname,vector<Node*>nodes):name(n......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99