树上启发式合并

可能很多人对启发式没啥概念，根本不知道啥是启发式。

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

当然在这里我们只涉及树上启发式合并（ d s u dsu dsu o n on on t r e e tree tree）

还有启发式合并伸展树（ S p l a y Splay Splay），线段树， m a p map map， s e t set set……

从一道例题入手：

给出一棵 n n n个节点以 1 1 1为根的树，节点 u u u的颜色为 c o l u col_u colu​ ，现在对于每个结点 i i i询问以 i i i为根的子树里一共出现了多少种不同的颜色。

n > 2 ∗ 1 0 5 n>2*10^5 n>2∗105

这道题如果要暴力跑每个节点为根的情况，每次要开一个 c n t cnt cnt数组存所有子树的颜色出现的次数，访问量巨大，即使预处理也只能优化到 O ( n 2 ) O(n^2) O(n2) 。

那我直接把计算的结果保留下来不就好了，看上去 O ( n ) O(n) O(n)的解法，实际上得开二维数组存数据。

这时候树上启发式合并就是你的不二选择！

个人对 d s u dsu dsu o n on on t r e e tree tree的理解：对于一个节点来说，处理重子树的信息要保留，所有轻子树的信息舍去（一般建立在要计算所有子树的贡献但是存储不了所有子树的信息的基础上）,将暴力的 O ( n 2 ) O(n^2) O(n2)优化到 O ( n l o g n ) O(nlogn) O(nlogn)

t i p s : tips: tips:对于一个节点 u u u所有的子树，子树节点数量最多的称为节点 u u u的重子树，除了重子树以外的子树叫轻子树。

算法基本思路（对于要处理的节点 u u u )

1. 处理轻子树的所有结果，计算答案。（但不保留对 c n t cnt cnt数组的影响（也就是说处理完之后，要把对 c n t cnt cnt数组的影响删除））
2. 处理重子树的结果。（保留对 c n t cnt cnt数组的影响）
3. 处理轻子树，参照重子树的保留结果对节点 u u u计算贡献。
4. 判断节点 u u u子树是不是父亲节点的重子树，如果不是，清除对 c n t cnt cnt数组的影响。

简而言之，在保留信息的数组只能开一维的情况下，只选择保留重子树的信息，对于轻子树的信息，处理完贡献要把它恢复成原来的模样。

#include 

#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 2e5+10;

template 
inline void read(_tp& x) {
	char ch = getchar(), sgn = 0;
	while (ch ^ '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') ch = getchar(), sgn = 1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	if (sgn) x = -x;
}

int col[maxn];
vectore[maxn];

int L[maxn], R[maxn], sz[maxn], totdfn;
int Node[maxn], big[maxn];
ll cnt[maxn], ans[maxn];
ll as;
void add(int u){
    if(!cnt[col[u]]) as++;
	cnt[col[u]]++;
}
void del(int u){
	cnt[col[u]]--;
    if(!cnt[col[u]]) as--;
}
void dfs1(int u, int fa){
	L[u] = ++totdfn;
	Node[totdfn] = u;
	sz[u] = 1;
	for(int v: e[u]){
		if(v == fa) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if(!big[u] || sz[big[u]] < sz[v]) big[u] = v;
	}
	R[u] = totdfn;
}

void dfs2(int u, int fa, bool keep){
	for(int v: e[u]){
		//cout << v << endl;
		if(v == fa || big[u] == v) continue;
		dfs2(v, u, false);
	}
	if(big[u]) dfs2(big[u], u, true);
	for(int v: e[u]){
		if(v == fa || big[u] == v) continue;
		for(int i = L[v]; i <= R[v]; ++i){
			add(Node[i]);
		}
	}
	//cout << tmp << endl;
	add(u);
	ans[u] = as;
	if(keep == false){
		for(int i = L[u]; i <= R[u]; ++i){
			del(Node[i]);
		}
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> col[i];
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1, 0);
	dfs2(1, 0, false);
	for(int i = 1; i <= n; ++i)
		cout << ans[i] << " ";
	return 0;
}

t i p s tips tips：当然也没必要 [ L [ u ] , R [ u ] ] [L[u], R[u] ] [L[u],R[u]] 遍历，递归遍历也可行。

CF600E

题意：

• 有一棵 n n n 个结点的以 1 1 1 号结点为根的有根树。
• 每个结点都有一个颜色，颜色是以编号表示的， i i i号结点的颜色编号为 c i c_i ci​。
• 如果一种颜色在以 x x x 为根的子树内出现次数最多，称其在以 x x x为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
• 你的任务是对于每一个 i ∈ [ 1 , n ] iin[1,n] i∈[1,n]，求出以 ii 为根的子树中，占主导地位的颜色的编号和。
• n ≤ 1 0 5 , c i ≤ n nle 10^5,c_ile n n≤105,ci​≤n

入门题，对着板子改一改就行

保留重子树的最大值，跑所有轻子树更新最大值即可

#include 

#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 1e5+10;

template 
inline void read(_tp& x) {
	char ch = getchar(), sgn = 0;
	while (ch ^ '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') ch = getchar(), sgn = 1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	if (sgn) x = -x;
}

int col[maxn];
vectore[maxn];

int L[maxn], R[maxn], sz[maxn], totdfn;
int Node[maxn], big[maxn];
ll cnt[maxn], ans[maxn];
ll mx = 0, tmp = 0;
void add(int u){
	cnt[col[u]]++;
	if(cnt[col[u]] > mx){
		mx = cnt[col[u]];
		tmp = col[u];
	}
	else if(cnt[col[u]] == mx) tmp += col[u];
}

void del(int u){
	cnt[col[u]]--;
}
void dfs1(int u, int fa){
	L[u] = ++totdfn;
	Node[totdfn] = u;
	sz[u] = 1;
	for(int v: e[u]){
		if(v == fa) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if(!big[u] || sz[big[u]] < sz[v]) big[u] = v;
	}
	R[u] = totdfn;
}

void dfs2(int u, int fa, bool keep){
	for(int v: e[u]){
		//cout << v << endl;
		if(v == fa || big[u] == v) continue;
		dfs2(v, u, false);
	}
	if(big[u]) dfs2(big[u], u, true);
	for(int v: e[u]){
		if(v == fa || big[u] == v) continue;
		for(int i = L[v]; i <= R[v]; ++i){
			add(Node[i]);
		}
	}
	//cout << tmp << endl;
	add(u);
	ans[u] = tmp;
	if(keep == false){
		for(int i = L[u]; i <= R[u]; ++i){
			del(Node[i]);
		}
		tmp = mx = 0;
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> col[i];
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1, 0);
	dfs2(1, 0, false);
	for(int i = 1; i <= n; ++i)
		cout << ans[i] << " ";
	return 0;
}

题意：一颗以 1 1 1为根的树，计算每个节点为根的子树下，所有相同颜色的节点两两最短路径之和

其实是一道很简单的题

题解：对于一个节点 u u u，儿子 v 1 , v 2 … … v n v_1,v_2……v_n v1​,v2​……vn​，子树的同颜色节点出现有两种情况

① 在同一颗子树下，通过跑 d s u dsu dsu o n on on t r e e tree tree其实都已经得出答案了 a n s [ u ] + = a n s [ v ] ans[u] += ans[v] ans[u]+=ans[v]即可

② 在不同子树下，那就得计算 v i v_i vi​对 u u u贡献了。假设我现在要加入一个点 v i v_i vi​，在另外一个子树上有一个点 v f v_f vf​（都为同一种颜色），那么 v i v_i vi​对 v f v_f vf​的贡献为 d e p [ v i ] − d e p [ u ] + d e p [ v f ] − d e p [ u ] dep[v_i]-dep[u]+dep[v_f]-dep[u] dep[vi​]−dep[u]+dep[vf​]−dep[u]，我们现在已知前面的子树里此颜色已经加入了 c n t cnt cnt个点， w = ∑ j = 1 c n t d e p [ j ] w = sum_{j=1}^{cnt}{dep[j]} w=∑j=1cnt​dep[j]，那么对于要加入的 v i v_i vi​点产生的贡献为 c n t ∗ ( d e p [ v i ] − d e p [ u ] ) + ( w − c n t ∗ d e p [ u ] ) cnt*(dep[v_i]-dep[u])+(w-cnt*dep[u]) cnt∗(dep[vi​]−dep[u])+(w−cnt∗dep[u]) 当然这只是处理一种颜色，对于多种颜色，开一个数组存一下不同颜色的深度和就行了。

#include 

#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 1e5+10;

template 
inline void read(_tp& x) {
	char ch = getchar(), sgn = 0;
	while (ch ^ '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') ch = getchar(), sgn = 1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	if (sgn) x = -x;
}

int col[maxn];
vectore[maxn];

int L[maxn], R[maxn], sz[maxn], totdfn;
int Node[maxn], big[maxn], h[maxn];
ll cnt[maxn], ans[maxn], col_ans[maxn];
ll tmp = 0;

void add_ans(int u, int root, int f){
    tmp += 1ll*cnt[col[u]]*(h[u]-h[root])*f + 1ll*(col_ans[col[u]]-cnt[col[u]]*h[root])*f;
}
void add(int u, int root, int f){
	cnt[col[u]] += f;
    col_ans[col[u]] += f * h[u];
}

void dfs1(int u, int fa, int dep){
	L[u] = ++totdfn;
	Node[totdfn] = u;
	sz[u] = 1;
    h[u] = dep;
	for(int v: e[u]){
		if(v == fa) continue;
		dfs1(v, u, dep+1);
		sz[u] += sz[v];
		if(!big[u] || sz[big[u]] < sz[v]) big[u] = v;
	}
	R[u] = totdfn;
}

void dfs2(int u, int fa, bool keep){
	for(int v: e[u]){
		if(v == fa || big[u] == v) continue;
		dfs2(v, u, false);
	}
	if(big[u]) dfs2(big[u], u, true);
    tmp = ans[big[u]];
	for(int v: e[u]){
		if(v == fa || big[u] == v) continue;
        tmp += ans[v];
		for(int i = L[v]; i <= R[v]; ++i){
			add_ans(Node[i], u, 1);   
		}
        for(int i = L[v]; i <= R[v]; ++i){
			add(Node[i], u, 1);  
		}
	}
	add_ans(u, u, 1);
    ans[u] = tmp;
    add(u, u, 1);
	if(keep == false){
		for(int i = L[u]; i <= R[u]; ++i){
			add(Node[i], u, -1);
		}
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> col[i];
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1, 0, 1);
	dfs2(1, 0, false);
	for(int i = 1; i <= n; ++i)
		cout << ans[i] << " ";
	return 0;
}