CSUOJ1811 Tree Intersection (启发式合并)
2024-10-11 15:22:54
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(bi,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).
OutputFor 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
Hint
题解:题意就是,给以一颗树n个节点,每个节点有一种颜色,然年后对于n-1条边,如果把一条边截断,让你求两颗子树有多少种相同的颜色,依次输入每一条边的答案。
启发式搜索,分别记录点和边的答案;如果点u和其子树某种颜色的数量已经等于总量了,那么对于该子树外的一部分,就没有该中颜色了,答案-1;如果小于总量,答案+1;
然后更新u节点该颜色的数量即可;
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define clr(a,val) memset(a,val,sizeof (a))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int maxn=1e5+;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
struct Edge{
int to,index,nxt;
} edge[maxn<<];
int n,head[maxn<<],tot;
int col[maxn],sum[maxn],ans[maxn],res[maxn<<];//ans[u]表示u点及子节点的答案, res[edge]表示边的答案
map<int,int> cnt[maxn];//cnt[u][color] 表示u点子树color颜色有多少个节点 inline void Init()
{
clr(head,-);clr(sum,); tot=;
for(int i=;i<=n;++i) cnt[i].clear();
} inline void addedge(int u,int v,int id)
{
edge[tot].to=v;
edge[tot].index=id;
edge[tot].nxt=head[u];
head[u]=tot++;
} inline void dfs(int u,int fa,int id)
{
cnt[u][col[u]]=;
ans[u] = cnt[u][col[u]]<sum[col[u]]?:;
for(int e=head[u];~e;e=edge[e].nxt)
{
int v=edge[e].to;
if(v==fa) continue;
dfs(v,u,edge[e].index);
if(cnt[u].size()<cnt[v].size())
{
swap(cnt[u],cnt[v]);
swap(ans[u],ans[v]);
}
map<int,int>::iterator it;
for(it=cnt[v].begin();it!=cnt[v].end();it++)
{
if(!cnt[u][(*it).fi] && (*it).se<sum[(*it).fi]) ++ans[u];
else if(cnt[u][(*it).fi] && cnt[u][(*it).fi]+(*it).se==sum[(*it).fi]) --ans[u];
cnt[u][(*it).fi]+=(*it).se;//加上子树的数量
}
}
res[id]=ans[u];
} int main()
{
while(~scanf("%d",&n))
{
Init();
for(int i=;i<=n;++i) col[i]=read(),sum[col[i]]++;
for(int i=;i<n;++i)
{
int u=read(),v=read();
addedge(u,v,i);addedge(v,u,i);
}
dfs(,,);
for(int i=;i<n;++i) printf("%d\n",res[i]);
} return ;
}
最新文章
- ABP理论学习之仓储
- nginx基于IP的虚拟主机
- bzoj 1858: [Scoi2010]序列操作
- git冲突的发生和解决/git workspace关于git的配置
- Codeforces Round #124 (Div. 2)
- PHP使用phpexcel读取excel文件
- 百度 迷你版 UMeditor富文本编辑器 使用方法
- 用Chrome开发者工具做JavaScript性能分析
- Google HTML/CSS 编码规范
- Sevrlet 工作原理解析-转
- Redis协议规范(RESP)
- linux服务器开机启动tomcat
- [线段树]HDU-1754板子题入门ver
- java第六章异常
- 天使玩偶:CDQ分治
- Java编程的逻辑 (13) - 类
- 在 Mac 上使用多点触控手势
- python(39):argparse的用法,从外部传入指定参数
- 终于在nowcoder爆发了的懒惰
- 【Oracle】存储过程在字符串单引号&#39;内拼接单引号&#39;
热门文章
- [LC]643题 Maximum Average Subarray I(子数组最大平均数 I)
- JS如何在不给新空间的情况下给数组去重?
- Linux注意事项
- opencv MatchTemplate()模板匹配寻找最匹配部分
- 你必须知道的容器日志 (2) 开源日志管理方案 ELK
- 16 Zabbix4.4.1系统告警“Zabbix agent is not available (for 3m)“
- Swoft源码之Swoole和Swoft的分析
- 护网杯一道crypto
- 性能测试——记weblogic 连接池满无法链接故障诊断过程
- html基础——表格练习