U41492 树上数颜色(dsu)「建议收藏」

U41492 树上数颜色(dsu)「建议收藏」U41492树上数颜色题意:输入n(1e5)n(1e5)n(1e5)表示一棵根为1的树有nnn个节点接下来n−1n-1n−1行每行u,vu,vu,v表示树边接下来一行nnn个数,c1,c2,…,cn(1≤ci≤n)c_1,c_2,\dots,c_n(1\leqc_i\leqn)c1​,c2​,…,cn​(1≤ci​≤n)表示节点颜色接下来m(m≤n)m(m\leqn)m(m≤n)…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

U41492 树上数颜色

题意:

输入 n ( 1 e 5 ) n(1e5) n(1e5)表示一棵根为1的树 n n n个节点
接下来 n − 1 n-1 n1行每行 u , v u,v u,v表示树边
接下来一行 n n n个数, c 1 , c 2 , … , c n ( 1 ≤ c i ≤ n ) c_1,c_2,\dots,c_n(1\leq c_i\leq n) c1,c2,,cn(1cin)表示节点颜色
接下来 m ( m ≤ n ) m(m\leq n) m(mn)个询问,每个询问询问一颗子树有多少个颜色。

题意:

用树上启发式合并(dsu)
先重链剖分出重儿子。
操作

  • 先处理轻儿子,并把结果消去
  • 处理重儿子,把结果保留
  • 最后把轻儿子的贡献加上

做法很暴力,但是复杂度就是 n log ⁡ ( n ) n\log(n) nlog(n)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int c[N],ans[N];
struct Edge{ 

int v,nxt;
}e[N<<1];
int head[N],cnt;
int n;
inline void add(int u,int v){ 

e[cnt]=(Edge){ 
v,head[u]};
head[u]=cnt++;
}
int son[N],siz[N];
void dfs(int u,int fa){ 

siz[u]=1;
for(int i=head[u];~i;i=e[i].nxt){ 

Edge e1=e[i];
if(e1.v==fa)continue;
dfs(e1.v,u);
siz[u]+=siz[e1.v];
if(siz[son[u]]<siz[e1.v])son[u]=e1.v;
}
}
int he[N],nowson,sum;
void calc(int u,int fa,int val){ 

// cout<<"calc "<<u<<" "<<fa<<" "<<val<<endl;
if(!he[c[u]])sum++;
he[c[u]]+=val;
for(int i=head[u];~i;i=e[i].nxt){ 

Edge e1=e[i];
if(e1.v==fa||e1.v==nowson)continue;
calc(e1.v,u,val);
}
}
void dsu(int u,int fa,bool kep){ 

// cout<<"dsu "<<u<<" "<<fa<<" "<<kep<<endl;
for(int i=head[u];~i;i=e[i].nxt){ 

Edge e1=e[i];
if(e1.v==fa||e1.v==son[u])continue;
dsu(e1.v,u,0);
}
if(son[u])dsu(son[u],u,1),nowson=son[u];
calc(u,fa,1);nowson=0;
ans[u]=sum;
if(!kep){ 

calc(u,fa,-1);
sum=0;
}
}
int main(){ 

// freopen("tt.in","r",stdin),freopen("tt.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
memset(head,-1,sizeof(head));
for(int i=1,u,v;i<n;i++){ 

cin>>u>>v;
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++)cin>>c[i];
dfs(1,0);
dsu(1,0,1);
int m;
cin>>m;
while(m--){ 

int t;
cin>>t;
cout<<ans[t]<<endl;
}
return 0;
}

Jetbrains全家桶1年46,售后保障稳定

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/230924.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux零拷贝_Linux开发教程

    Linux零拷贝_Linux开发教程引言传统的Linux操作系统的标准I/O接口是基于数据拷贝操作的,即I/O操作会导致数据在操作系统内核地址空间的缓冲区和应用程序地址空间定义的缓冲区之间进行传输。这样做最大的好处是可以减少磁盘I/O的操作,因为如果所请求的数据已经存放在操作系统的高速缓冲存储器中,那么就不需要再进行实际的物理磁盘I/O操作。但是数据传输过程中的数据拷贝操作却导致了极大的CPU开销,限

  • listagg()行转列函数[通俗易懂]

    listagg()行转列函数[通俗易懂]–基础数据DROPTABLE"ZYH_TEST";CREATETABLE"ZYH_TEST"("ID"NUMBER(19)NOTNULL,"NAME"VARCHAR2(255BYTE),"CREATETIME"DATE,"SCORE"NUMBER,"CLASSID"VARCHAR2(255BYTE)

  • pycharm2022激活码【2021免费激活】

    (pycharm2022激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 惠普电脑蓝屏开不了机怎么解决_hp服务器售后电话800

    惠普电脑蓝屏开不了机怎么解决_hp服务器售后电话800在日常生活中,电脑出现蓝屏的无法启动的问题很常见,怎么处理电脑蓝屏问题呢?下面是小编为大家整理的关于hp电脑蓝屏后无法启动的相关资料,希望对您有所帮助!hp电脑蓝屏后无法启动的解决方法很多时候电脑蓝屏是因为电脑的硬件,电脑关机完成后,我们可以断开电脑的电源,然后对我们的内存条擦拭后,从新装机到我们的电脑主板上。清理电脑的各项主板接口也是必须的,我们可以根据顺序,依次清理电脑的各个接口,完成后即可。…

  • 3DE平台基础_系统架构师多少分过

    3DE平台基础_系统架构师多少分过3DE平台系统架构

  • String如何截取字符串长度

    String如何截取字符串长度20应届生面试题:使用String引用类型的时候,用过哪些方法?比如如何截取一段给定字符串的长度?答:没回答上来!(没用过截取字符串)String引用类型中有一个叫做substring的方法,这个就是用来截取字符串的。Ctrl+鼠标左键点进了substring方法内,查看到了以下源码。//小白的理解://beginIndex是起始位置,endIndex是末端位置publicStringsubstring(intbeginIndex,intendIndex){

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号