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

全栈程序员站长

发布于 2022-11-16 18:05:18

3320

发布于 2022-11-16 18:05:18

U41492 树上数颜色

题意：

输入 n ( 1 e 5 ) n(1e5) n(1e5)表示一棵根为1的树有 n n n个节点接下来 n − 1 n-1 n−1行每行 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(1≤ci≤n)表示节点颜色接下来 m ( m ≤ n ) m(m\leq n) m(m≤n)个询问,每个询问询问一颗子树有多少个颜色。

题意：

用树上启发式合并(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，售后保障稳定

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/230924.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月31日，如有侵权请联系 cloudcommunity@tencent.com 删除

https