U41492 树上数颜色(dsu on tree)
2021/8/6 23:09:53
本文主要是介绍U41492 树上数颜色(dsu on tree),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
blackpink
\(O(n^2)\)显然不过我们应该优化成\(O(nlogn)\)
采用树上启发式合并
仿照树链剖分的思想,对于每一个位置,我们先处理所有的轻儿子,然后处理重儿子,统计当前节点的答案,最后把轻儿子删掉就可以了。
这样全局一个桶就够用了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n; int x,y; int col[1000005]; struct e{ int to; int ne; }ed[3000005]; int p; int head[1000005]; void add(int f,int to){ p++; ed[p].to=to; ed[p].ne=head[f]; head[f]=p; return ; } int siz[2000005]; int ns; int ans[2000005]; int tem; int son[1000005]; int exi[1000005]; void dfs(int no,int fa){ siz[no]++; for(int i=head[no];i;i=ed[i].ne){ if(ed[i].to==fa) continue; dfs(ed[i].to,no); siz[no]+=siz[ed[i].to]; if(siz[ed[i].to]>siz[son[no]]){ son[no]=ed[i].to; } } } void work(int no,int fa,int ke){ if(!exi[col[no]]){ tem++; } exi[col[no]]+=ke; for(int i=head[no];i;i=ed[i].ne){ int v=ed[i].to; if(v==fa||v==ns) continue; work(v,no,ke); } } void dsu(int no,int fa,int f){ for(int i=head[no];i;i=ed[i].ne){ if(ed[i].to==fa||ed[i].to==son[no]) continue; dsu(ed[i].to,no,0); } if(son[no]) { dsu(son[no],no,1); ns=son[no]; } work(no,fa,1); ns=0; ans[no]=tem; if(!f){ work(no,fa,-1); tem=0; } } int main(){ scanf("%d",&n); for(int i=1;i<n;++i){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;++i){ scanf("%d",&col[i]); } dfs(1,0); //cout<<2344; dsu(1,0,1); scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&x); printf("%d\n",ans[x]); } return 0; }
这篇关于U41492 树上数颜色(dsu on tree)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现