首页 > 其他分享 >树论

树论

时间：2024-08-15 15:09:12浏览次数：5  
标签：node nxt cur int 树论 son root

树论

LCT

class C_LinkCutTree
{
public:
	int rev[N], fa[N], ch[N][2];
	/*====================*/
	bool Which(int x)
	{
		return ch[fa[x]][1] == x;
	}
	bool IsRoot(int x)
	{
		return ch[fa[x]][Which(x)] != x;
	}
	/*====================*/
	void PushUp(int x)
	{
		/*PushUp*/
	}
	void PushAll(int x)
	{
		if (!IsRoot(x))
		{
			PushAll(fa[x]);
		}
		PushDown(x);
	}
	void PushDown(int x)
	{
		if (rev[x])
		{
			swap(ch[x][0], ch[x][1]);
			rev[ch[x][0]] ^= 1;
			rev[ch[x][1]] ^= 1;
			rev[x] = 0;
		}
		/*PushDown*/
	}
	/*====================*/
	void Rotate(int x)
	{
		int y = fa[x], z = fa[y], w = Which(x);
		if (!IsRoot(y)) ch[z][Which(y)] = x; fa[x] = z;
		ch[y][w] = ch[x][w ^ 1];
		if (ch[y][w]) fa[ch[y][w]] = y;
		ch[x][w ^ 1] = y; fa[y] = x;
		PushUp(y); PushUp(x);
	}
	void Splay(int x)
	{
		PushAll(x);
		for (; !IsRoot(x); Rotate(x))
		{
			if (!IsRoot(fa[x]))
			{
				Rotate(Which(x) == Which(fa[x]) ? fa[x] : x);
			}
		}
	}
	/*====================*/
	void Access(int x)
	{
		for (int p = 0; x; p = x, x = fa[x])
		{
			Splay(x), ch[x][1] = p, PushUp(x);
		}
	}
	/*====================*/
	int FindRoot(int x)
	{
		Access(x); Splay(x);
		while (ch[x][0]) x = ch[x][0];
		Splay(x); return x;
	}
	void MakeRoot(int x)
	{
		Access(x); Splay(x); rev[x] ^= 1;
	}
	/*====================*/
	void Cut(int u, int v)
	{
		Split(u, v);
		if (fa[u] == v && !ch[u][1])
		{
			ch[v][0] = fa[u] = 0;
		}
	}
	void Link(int u, int v)
	{
		MakeRoot(u); fa[u] = v;
	}
	/*====================*/
	void Split(int u, int v)
	{
		MakeRoot(u); Access(v); Splay(v);
	}
	/*====================*/
	int LCA(int u, int v)
	{
		Access(u); int ans = 0;
		for (int child = 0; v; child = v, v = fa[v])
		{
			Splay(v); ch[v][1] = child; ans = v;
		}
		return ans;
	}
};

LCA

树剖法

class C_LCA
{
private:
	struct Node
	{
		int pre, dep, siz, son, top;
		Node(void)
		{
			pre = -1, dep = +0, siz = +1, son = -1, top = -1;
		}
	};
	/*====================*/
	int root;
	vector<int>* G;
	vector<Node>node;
	/*====================*/
	void DFS1(int pre, int cur)
	{
		node[cur].pre = pre;
		node[cur].dep = node[pre].dep + 1;
		for (auto nxt : G[cur])
		{
			if (nxt != pre)
			{
				DFS1(cur, nxt);
				node[cur].siz += node[nxt].siz;
				if (node[cur].son == -1)
				{
					node[cur].son = nxt;
				}
				else if (node[nxt].siz > node[node[cur].son].siz)
				{
					node[cur].son = nxt;
				}
			}
		}
	}
	void DFS2(int cur, int top)
	{
		node[cur].top = top;
		if (node[cur].son != -1)
		{
			DFS2(node[cur].son, top);
			for (auto nxt : G[cur])
			{
				if (nxt == node[cur].pre)continue;
				if (nxt == node[cur].son)continue;
				DFS2(nxt, nxt);
			}
		}
	}
public:
	void Init(int n, vector<int>G[], int root = 1)
	{
		this->G = G;
		this->root = root;
		node.assign(n + 1, Node());
		DFS1(root, root); DFS2(root, root);
	}
	int operator()(int u, int v)
	{
		while (node[u].top != node[v].top)
		{
			int topu = node[u].top;
			int topv = node[v].top;
			if (node[topu].dep > node[topv].dep)
			{
				u = node[topu].pre;
			}
			else
			{
				v = node[topv].pre;
			}
		}
		return node[u].dep > node[v].dep ? v : u;
	}
};

ST表法

class C_LCA
{
private:
	vector<int>* G;
	vector<int>dfn;
	vector<vector<int>>table;
	/*====================*/
	void DFS(int pre, int cur)
	{
		table[0][dfn[cur] = ++dfn[0]] = pre;
		for (auto nxt : G[cur])if (nxt != pre)DFS(cur, nxt);
	}
	int Get(int x, int y)
	{
		return dfn[x] < dfn[y] ? x : y;
	}
public:
	void Init(int n, vector<int>G[], int root = 1)
	{
		this->G = G; dfn.assign(n + 1, 0);
		table.assign(__lg(n) + 1, vector<int>(n + 1, 0));
		/*====================*/
		DFS(0, root);
		for (int d = 1; (1 << d) <= n; ++d)
		{
			for (int i = 1; i + (1 << d) - 1 <= n; ++i)
			{
				table[d][i] = Get(table[d - 1][i], table[d - 1][i + (1 << (d - 1))]);
			}
		}
	}
	int operator()(int u, int v)
	{
		if (u == v)return u;
		if ((u = dfn[u]) > (v = dfn[v]))swap(u, v);
		int d = __lg(v - u++); return Get(table[d][u], table[d][v - (1 << d) + 1]);
	}
};

树哈希

class C_TreeHash
{
private:
	vector<int>* G;
	map<vector<int>, int>mp;
	/*====================*/
	int DFS(int pre, int cur)
	{
		vector<int>vec;
		for (auto nxt : G[cur])
		{
			if (nxt != pre)
			{
				vec.push_back(DFS(cur, nxt));
			}
		}
		sort(vec.begin(), vec.end());
		if (mp.find(vec) == mp.end())
		{
			mp[vec] = mp.size();
		}
		return mp[vec];
	}
public:
	int operator()(vector<int>G[], int root)
	{
		this->G = G;
		return DFS(root, root);
	}
};

树分治

点分治

class C_TCD
{
private:
	vector<int>* G;
	/*====================*/
	vector<int>siz;
	vector<bool>rooted;
	/*====================*/
	int centroid, ans_part;
	/*====================*/
	void DFS(int pre, int cur, int all)
	{
		siz[cur] = 1; int max_part = 0;
		for (auto nxt : G[cur])
		{
			if (nxt == pre)continue;
			if (rooted[nxt])continue;
			DFS(cur, nxt, all);
			siz[cur] += siz[nxt];
			max_part = max(max_part, siz[nxt]);
		}
		max_part = max(max_part, all - siz[cur]);
		if (max_part < ans_part)
		{
			ans_part = max_part, centroid = cur;
		}
	}
	int Centroid(int cur, int all)
	{
		centroid = -1; ans_part = all;
		DFS(cur, cur, all); return centroid;
	} 
	/*====================*/
	void CalcSon(int pre, int cur)
	{
		/*
			添加cur到右树tree中
		*/
		for (auto nxt : G[cur])
		{
			if (nxt == pre)continue;
			if (rooted[nxt])continue;
			CalcSon(cur, nxt);
		}
	}
	void CalcRoot(int root)
	{
		/*
			初始化左库lib
		*/
		for (auto son : G[root])
		{
			if (!rooted[son])
			{
				/*
					初始化右树tree
				*/
				CalcSon(son, son);
				/*
					遍历右树tree匹配左库lib
				*/
				/*
					添加右树tree到左库lib
				*/
			}
		}
	}
	/*====================*/
	void DividTree(int root)
	{
		rooted[root] = true; CalcRoot(root);
		for (auto son : G[root])
		{
			if (!rooted[son])
			{
				DividTree(Centroid(son, siz[son]));
			}
		}
	}
public:
	void operator()(int n, vector<int>G[])
	{
		this->G = G;
		siz.assign(n + 1, 0);
		rooted.assign(n + 1, false);
		DividTree(Centroid(1, n));
	}
};

K级祖先

class C_KthAncestor
{
private:
	int n, root; vector<int>* G;
	/*====================*/
	struct Node
	{
		int pre, dep, siz, son;
		int top, dfn, idx;
		Node(void)
		{
			pre = -1; dep = +0;
			siz = +1; son = -1;
			dfn = +0, idx = +0;
			top = -1;
		}
	};
	/*====================*/
	vector<Node>node; int cnt;
	/*====================*/
	void DFS1(int pre, int cur)
	{
		node[cur].pre = pre;
		node[cur].dep = node[pre].dep + 1;
		for (auto nxt : G[cur])
		{
			if (nxt != pre)
			{
				DFS1(cur, nxt); node[cur].siz += node[nxt].siz;
				if (node[cur].son == -1)
				{
					node[cur].son = nxt;
				}
				else if (node[nxt].siz > node[node[cur].son].siz)
				{
					node[cur].son = nxt;
				}
			}
		}
	}
	void DFS2(int cur, int top)
	{
		node[cur].top = top;
		node[cur].dfn = ++cnt;
		node[cnt].idx = cur;
		if (node[cur].son != -1)
		{
			DFS2(node[cur].son, top);
			for (auto nxt : G[cur])
			{
				if (nxt == node[cur].pre)continue;
				if (nxt == node[cur].son)continue;
				DFS2(nxt, nxt);
			}
		}
	}
public:
	void Init(int n, vector<int>G[], int root = 1)
	{
		node.assign(n + 1, Node());
		this->n = n, this->root = root, this->G = G;
		cnt = 0; DFS1(root, root); DFS2(root, root);
	}
	int operator()(int x, int k)
	{
		int topx = node[x].top;
		while (k > 0)
		{
			topx = node[x].top;
			if (node[x].dep - node[topx].dep < k)
			{
				k -= node[x].dep - node[topx].dep + 1;
				x = node[topx].pre;
			}
			else
			{
				x = node[node[x].dfn - k].idx; k = 0;
			}
		}
		return x;
	}
};

树链剖分

重链剖分

class C_HLD
{
public:
	int n, root; vector<int>* G;
	/*====================*/
	struct Node
	{
		int pre, dep, siz, son;
		int top, dfn, idx;
		Node(void)
		{
			pre = -1; dep = +0;
			siz = +1; son = -1;
			dfn = +0, idx = +0;
			top = -1;
		}
	};
private:
	vector<Node>node; int cnt;
	/*====================*/
	void DFS1(int pre, int cur)
	{
		node[cur].pre = pre;
		node[cur].dep = node[pre].dep + 1;
		for (auto nxt : G[cur])
		{
			if (nxt != pre)
			{
				DFS1(cur, nxt); node[cur].siz += node[nxt].siz;
				if (node[cur].son == -1)
				{
					node[cur].son = nxt;
				}
				else if (node[nxt].siz > node[node[cur].son].siz)
				{
					node[cur].son = nxt;
				}
			}
		}
	}
	void DFS2(int cur, int top)
	{
		node[cur].top = top;
		node[cur].dfn = ++cnt;
		node[cnt].idx = cur;
		if (node[cur].son != -1)
		{
			DFS2(node[cur].son, top);
			for (auto nxt : G[cur])
			{
				if (nxt == node[cur].pre)continue;
				if (nxt == node[cur].son)continue;
				DFS2(nxt, nxt);
			}
		}
	}
public:
	void Init(int n, vector<int>G[], int root = 1)
	{
		node.assign(n + 1, Node());
		this->n = n, this->root = root, this->G = G;
		cnt = 0; DFS1(root, root); DFS2(root, root);
	}
	Node& operator[](int idx) { return node[idx]; }
};

树的重心

class C_TreeCentroid
{
private:
	vector<int>siz;
	vector<int>* G;
	int centroid, ans_part;
	/*====================*/
	void DFS(int pre, int cur, int all)
	{
		siz[cur] = 1; int max_part = 0;
		for (auto nxt : G[cur])
		{
			if (nxt != pre)
			{
				DFS(cur, nxt, all);
				siz[cur] += siz[nxt];
				max_part = max(max_part, siz[nxt]);
			}
		}
		max_part = max(max_part, all - siz[cur]);
		if (max_part < ans_part)
		{
			ans_part = max_part, centroid = cur;
		}
	}
public:
	int operator()(int n, vector<int>G[])
	{
		this->G = G; siz.assign(n + 1, 0);
		centroid = -1; ans_part = n;
		DFS(1, 1, n); return centroid;
	}
};

树上路径求交

假设当前要求路径 \((a,b)\) 和 \((c,d)\) 的交。
设 \(d_x\) 表示 \(x\) 的深度。
先求出 \(p[4]={lca(a,c),lca(a,d),lca(b,c),lca(b,d)}\)。
将 \(p\) 数组按深度排序，取出深度较大的两个，记为 \(p0,p1\)。
若存在交，则 \((p0,p1)\) 即所求。
现在只需要判断路径是否有交。
若 \(p0\neq p1\)，则一定有交。
否则若 \(d_{p0}=\max(d_{lca(a,b)},d_{lca(c,d)})\)，也有交。
否则路径不相交。

树上启发式合并

对于以 u 为根的子树

①. 先统计它轻子树(轻儿子为根的子树)的答案，统计完后删除信息

②. 再统计它重子树(重儿子为根的子树)的答案，统计完后保留信息

③. 然后再将重子树的信息合并到 u上

④. 再去遍历 u 的轻子树，然后把轻子树的信息合并到 u 上

⑤. 判断 u 的信息是否需要传递给它的父节点（u 是否是它父节点的重儿子）

void DFS(int root, int cur)
{
	cnt[node[cur].val]++;
	if (cnt[node[cur].val] > maxcnt)
	{
		ans[root] = node[cur].val;
		maxcnt = cnt[node[cur].val];
	}
	else if (cnt[node[cur].val] == maxcnt)
	{
		ans[root] += node[cur].val;
	}
	for (auto nxt : G[cur])
	{
		if (nxt == node[cur].pre)continue;
		if (nxt == node[root].son)continue;
		DFS(root, nxt);
	}
}
void DSU(int cur, bool keep)
{
	for (auto nxt : G[cur])
	{
		if (nxt == node[cur].pre)continue;
		if (nxt == node[cur].son)continue;
		DSU(nxt, false);
	}
	if (node[cur].son != -1)DSU(node[cur].son, true);
	if (node[cur].son != -1)
	{
		ans[cur] = ans[node[cur].son];
	}
	DFS(cur, cur);
	if (keep == false)
	{
		maxcnt = 0;
		for (int i = node[cur].dfn; i < node[cur].dfn + node[cur].siz; ++i)
		{
			cnt[node[node[i].idx].val]--;
		}
	}
}

标签：node,nxt,cur,int,树论,son,root
From： https://www.cnblogs.com/ProtectEMmm/p/18360926

相关文章

  • 树论题目整理01
    P3320[SDOI2015]寻宝游戏小B最近正在玩一个寻宝游戏，这个游戏的地图中有\(N\)个村庄和\(N-1\)条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该......
  • 树论（一）
    在“无限”的量中寻找“有限”的量——可能产生贡献的点对的数量不妨用两个log的时间复杂度进行预处理（都预处理了，就不要再想着判断合法性了）1~N每个数的约数个数的总和大约为NlogNu,v都在某个子树内等价于它们的【最近公共祖先】在该子树内，将点对的贡献打到LCA(i,j)上点击查......
  • 7.15 树论
    MilkVisitsG自己做出来哒！先考虑是一条链时怎么做。很显然，用set维护每种奶的位置，然后lowerbound查找\(l\)再判断是否合法即可。那么再放到树上来做，显然，直接树链剖分就可以把树转化成链。于是做完力！点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN......
  • 【树论典题】P5642 人造情感（emotion）
    P5642人造情感（emotion）随便挑点杂题做/kk。乐。不会做这个题，我难道还不会做CF856DMashaandCactus。先考虑后者怎么做？CF856DMashaandCactus乐。考虑在\(LCA\)上挂很多个chains.\[s_u=\sum_{v\inson_u}f_v,f_u=s_u\]\[t_i=\underset{(x_i,y_i,w_i)}......
  • 【树论】RMQ问题和ST表
    目录RMQ问题ST表优缺点实现递推查询复杂度代码技巧-快速读入RMQ问题RMQ（RangeMaximum/MinimumQuery）问题，即区间最值问题。一般是多次询问，对时间复杂度要求高，一般需要\(O(logn)\)或\(O(1)\)复杂度ST表p[i][j]是以i为起点，连续\(2^j\)个数字的最大值(是一个递推表)3......
  • 简单树论
    cmd的blog可以参考水平不高,内容比较简单.内容难度不随章节单增.0.杂七杂八做题做到什么东西都会扔到这里.想到啥写啥.如果要求统计树上所有点对之间的贡献,可以考虑枚举lca.(CF1856E1)如果有类似于树上经过的边的权值\(\leqk\)这样的限制,可以把边按照边......
  • 【树论，计数】Centroid Probabilities
    生生动动贺题贺一遍！考虑先求出\(f_x\)表示\(x\)子树大小\(\leq\frac{n+1}{2}\)的方案数。最后再容斥掉\(x+1\ton\)的方案即可。\[\sum^{n-x+1}_{j=\frac{n+1}{2}}\binom{n-i}{j-1}(j-1)!(n-j-1)!(i-1)\]即考虑选出子树，生成子树内和子树......
  • 【树论典题。】P6071 『MdOI R1』Treequery
    前言：输了，被水杯提醒我一直很失败。正片：简要题意求\([l,r]\top\)的路径的交的边权和。Solution：\(O(n\log^2n)\)巨大分讨做法。考虑分类讨论。其一，\(p\)根本就不属于路径上的点，这个求区间LCA可以解决\(p\toanc_{[l,r]}\)其二，\(p\)是\(anc_{l,r}\)的祖......
  • 7.27 day4 树论
    悲报：335->220战绩:100+100+20+0T1求子树sizeT2通过大眼观察严谨的证明后，我们发现\(x_i\)是\(x_i+1\)的祖先的概率和\(x_i+1\)具体是什么无关：我们令\(x_i+1\)一直跳父亲，直到编号小于等于\(x_i\)的那一次。因为父亲是等概率选取的，所以概率就是\(\frac{1}{x_i}\)......
  • 树论
    1.重链剖分1.1.简介重链剖分将树分割成若干链维护信息，将树的结构转换为线性结构，然后可用其他数据结构维护。定义以下概念：重子节点轻子节点重边轻边重链某节点的子节点中子树大小最大的那个某节点的子节点中的非重子节点由某节点到其重子节点的连边由某节点到......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99