图论|【启发式合并】例题 CodeForces-600E（子树颜色树上众数）+ CodeForces - 1009F（每层节点数的众数）+ CSU

例题一 Lomsat gelral CodeForces - 600E You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.
Let’s call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it’s possible that two or more colours will be dominating in the subtree of some vertex.
The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.
For each vertex v find the sum of all dominating colours in the subtree of vertex v.
Input
The first line contains integer n (1?≤?n?≤?105) — the number of vertices in the tree.
The second line contains n integers ci (1?≤?ci?≤?n), ci — the colour of the i-th vertex.
Each of the next n?-?1 lines contains two integers xj,?yj (1?≤?xj,?yj?≤?n) — the edge of the tree. The first vertex is the root of the tree.
Output
Print n integers — the sums of dominating colours for each vertex.
Examples
Input
4
1 2 3 4
1 2
2 3
2 4
Output
10 9 3 4
Input
15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
Output
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
题意：
给一棵树，每个节点有一种颜色，求每个节点v的子树上颜色众数的和。
思路：
启发式合并，记录子树中每种颜色出现的次数的同时，记录颜色出现次数最多的次数maxx，和出现次数为maxx的颜色值的和sum。
AC代码：

#include #include #include #include #include #include #include using namespace std; const int maxn = 1e5 + 100; int col[maxn], sz[maxn], son[maxn], cnt[maxn]; int n, big, maxx; long long ans[maxn], sum; vector G[maxn]; void get_son(int u, int p) { sz[u] = 1; int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p) { get_son(v, u); sz[u] += sz[v]; if(sz[v] > sz[son[u]]) son[u] = v; } } }void add(int u, int p, int x) { cnt[ col[u] ] += x; //先加自己的信息if(cnt[ col[u] ] > maxx)//记录出现最大的出现次数maxx { sum = col[u]; maxx = cnt[ col[u] ]; } else if(cnt[ col[u] ] == maxx)//求出现次数为maxx的颜色的和 { sum += col[u]; }int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != big)//只加上轻儿子 add(v, u, x); } }void dfs(int u, int p, bool keep) { int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != son[u])//先dfs求轻子节点的值，保存结果到ans中，并清空cnt dfs(v, u, 0); } if(son[u]) { dfs(son[u], u, 1); //再dfs求重子节点的值，保存结果到ans中，不清空cnt big = son[u]; }//此时cnt中已经有重儿子的信息了，再把轻儿子的加上，就得出u的ans了add(u, p, 1); //加上轻儿子big = 0; //重儿子标记清除ans[u] = sum; if(!keep) { add(u, p, -1); //轻儿子，要清空cnt maxx = 0; sum = 0; } }int main() { while(~scanf("%d", &n)) { big = 0; maxx = 0; sum = 0; for(int i = 1; i <= n; i++) { G[i].clear(); sz[i] = son[i] = cnt[i] = ans[i] = 0; } for(int i = 1; i <= n; i++) scanf("%d", &col[i]); int u, v; for(int i = 0; i < n - 1; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } get_son(1, 0); dfs(1, 0, 1); for(int i = 1; i <= n; i++) { if(i != 1) printf(" "); printf("%lld", ans[i]); } printf("\n"); } return 0; }

例题二 Dominant Indices CodeForces - 1009F You are given a rooted undirected tree consisting of n vertices. Vertex 1 is the root.
Let’s denote a depth array of vertex x as an infinite sequence [dx,0,dx,1,dx,2,…], where dx,i is the number of vertices y such that both conditions hold:

x is an ancestor of y;
the simple path from x to y traverses exactly i edges.

The dominant index of a depth array of vertex x
(or, shortly, the dominant index of vertex x) is an index j
such that:

for every k
for every k>j , dx,k≤dx,j .

For every vertex in the tree calculate its dominant index.
Input
The first line contains one integer n (1≤n≤10^6) — the number of vertices in a tree.
Then n?1 lines follow, each containing two integers x and y (1≤x,y≤n, x≠y ). This line denotes an edge of the tree.
It is guaranteed that these edges form a tree.
【图论|【启发式合并】例题 CodeForces-600E（子树颜色树上众数）+ CodeForces - 1009F（每层节点数的众数）+ CSU - 1811(去边后，求颜色并集大小)】Output
Output n numbers. i-th number should be equal to the dominant index of vertex i.
Examples
Input
4
1 2
2 3
3 4
Output
0
0
0
0
Input
4
1 2
1 3
1 4
Output
1
0
0
0
Input
4
1 2
2 3
2 4
Output
2
1
0
0
题意：
对于每一个节点x，可以定义一个深度数组[dx0,dx1,dx2,…dxh]，代表着以节点x为根往下计算，深度为h的那层的节点的数量。
对于每一个节点x，我们可以从深度数组中，选择一个主要索引下标j，作为他的代表。这个dj需要满足以下条件，他是所有dh中，最大的那个，如果有多个dh是一样的，都是最大的，那么选择j（即深度）最小的那个。
思路：
启发式合并。
对于每一个节点，预先处理出，相对于根节点（深度为1）来说，它的深度。那么在计算深度数组时的相对深度，就等于deep[儿子] - deep[父亲]。
这里其实是color的变种，将col变成了deep，我们只需要将cnt[ col ] 换成cnt [ deep ]即可，然后在add的过程中，记录cnt[ deep ]的最大值maxx，和这个maxx的deep作为id。然后ans中记录这个id。输出结果时，用ans[i] - deep[i]即可。
AC代码：

#include #include #include #include #include #include #include using namespace std; const int maxn = 1e6 + 100; int deep[maxn], sz[maxn], son[maxn], cnt[maxn], ans[maxn]; int n, big, maxx, id; vector G[maxn]; void get_son(int u, int p, int dp) { sz[u] = 1; deep[u] = dp; int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p) { get_son(v, u, dp + 1); sz[u] += sz[v]; deep[v] = deep[u] + 1; if(sz[v] > sz[son[u]]) son[u] = v; } } }void add(int u, int p, int x) { cnt[ deep[u] ] += x; if(cnt[ deep[u] ] > maxx) { id = deep[u]; maxx = cnt[ deep[u] ]; } else if(cnt[ deep[u] ] == maxx && deep[u] < id) { id = deep[u]; }int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != big) add(v, u, x); } }void dfs(int u, int p, bool keep) { int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != son[u]) dfs(v, u, 0); } if(son[u]) { dfs(son[u], u, 1); big = son[u]; } add(u, p, 1); big = 0; ans[u] = id; if(!keep) { add(u, p, -1); maxx = 0; id = 0; } }int main() { while(~scanf("%d", &n)) { big = 0; maxx = 0; id = 0; for(int i = 1; i <= n; i++) { G[i].clear(); sz[i] = son[i] = cnt[i] = ans[i] = 0; } int u, v; for(int i = 1; i < n; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } get_son(1, 0, 1); dfs(1, 0, 1); for(int i = 1; i <= n; i++) { printf("%d\n", ans[i] - deep[i]); } } return 0; }

例题三 Tree Intersection CSU - 1811 Bobo has a tree with n vertices numbered by 1,2,…,n and (n-1) edges. The i-th vertex has color c i, and the i-th edge connects vertices a i and b i.
Let C(x,y) denotes the set of colors in subtree rooted at vertex x deleting edge (x,y).
Bobo would like to know R_i which is the size of intersection of C(a i,b i) and C(b i,a i) for all 1≤i≤(n-1). (i.e. |C(a i,b i)∩C(b i,a i)|)
Input
The input contains at most 15 sets. For each set:
The first line contains an integer n (2≤n≤10 5).
The second line contains n integers c 1,c 2,…,c n (1≤c_i≤n).
The i-th of the last (n-1) lines contains 2 integers a i,b i (1≤a i,b i≤n).
Output
For each set, (n-1) integers R 1,R 2,…,R n-1.
Sample Input
4
1 2 2 1
1 2
2 3
3 4
5
1 1 2 1 2
1 3
2 3
3 5
4 5
Sample Output
1
2
1
1
1
2
1
题意：
给一棵带有颜色的树，去掉某一条边后，他就变成了两个连通块，求这两个连通块的颜色交集的大小。（对每条边求一次）
思路：
整棵树的颜色可以预处理出来，去掉一条边后，就变成了一颗子树，和剩余的树，可以将子树的颜色处理出来，然后剩余的那棵树的颜色也求出来了（等于整树减去子树）。
子树可以用启发式合并求。
注意子树cnt 和剩余树 num - cnt 的比较，要放在每一次add时比较（和上面的col一样），而不能放在dfs里（每次add完后，再统一比较cnt 和 num - cnt），否则会超时。
AC代码：

#include #include using namespace std; const int maxn = 1e5 + 5; int son[maxn], cnt[maxn], ans[maxn]; int n, big, sum; int eu[maxn], ev[maxn]; int col[maxn], num[maxn], sz[maxn], deep[maxn]; vector G[maxn]; void get_son(int u, int p, int dp) { sz[u] = 1; deep[u] = dp; int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p) { get_son(v, u, dp + 1); sz[u] += sz[v]; deep[v] = dp + 1; if(sz[v] > sz[son[u]]) son[u] = v; } } }void add(int u, int p, int x) { cnt[ col[u] ] += x; if(cnt[ col[u] ] == 1) sum++; ; if(cnt[ col[u] ] == num[ col[u] ]) sum--; int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != big) add(v, u, x); } }void dfs(int u, int p, bool keep) { int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != son[u]) dfs(v, u, 0); } if(son[u]) { dfs(son[u], u, 1); big = son[u]; } add(u, p, 1); big = 0; int t = 0; ans[u] = sum; if(!keep) { add(u, p, -1); sum = 0; } }int main() { while(~scanf("%d", &n)) { big = 0; sum = 0; for(int i = 1; i <= n; i++) { G[i].clear(); num[i] = sz[i] = son[i] = cnt[i] = ans[i] = 0; } for(int i = 1; i <= n; i++) { scanf("%d", &col[i]); num[ col[i] ]++; } int u, v; for(int i = 1; i < n; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); eu[i] = u; ev[i] = v; } get_son(1, 0, 1); dfs(1, 0, 1); for(int i = 1; i < n; i++) { int a = deep[ eu[i] ] > deep[ ev[i] ] ? eu[i] : ev[i]; printf("%d\n", ans[a]); } } return 0; }

写成下面这样就会超时：

void add(int u, int p, int x) { cnt[ col[u] ] += x; int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != big) add(v, u, x); } }void dfs(int u, int p, bool keep) { int len = G[u].size(); for(int i = 0; i < len; i++) { int v = G[u][i]; if(v != p && v != son[u]) dfs(v, u, 0); } if(son[u]) { dfs(son[u], u, 1); big = son[u]; } add(u, p, 1); big = 0; //统一比较 int t = 0; for(int i = 1; i <= n; i++) { if((num[i] - cnt[i]) && cnt[i]) t++; } //endans[u] = t; if(!keep) { add(u, p, -1); } }