图论|【启发式合并】例题 CodeForces-600E(子树颜色 树上众数)+ CodeForces - 1009F(每层节点数的众数)+ CSU - 1811(去边后,求颜色并集大小)
例题一 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.
(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 .
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);
}
}
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- 求桥,边双连通缩点
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- 玩一玩|超立方体及其可视化(Processing)
- #|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化
- 图论|POJ1364 King 差分约束
- 图论|tarjan算法之——割点和桥
- Codeforces 1076D Edge Deletion——最短路+dfs
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 贪心|Codeforces D. Solve The Maze (bfs & 贪心) (Round #648 Div.2)