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

编程汇总 • 2025-03-05 16:33 • 阅读 28

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

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]]
}

}

int he[N],nowson,sum;

void calc(int u,int fa,int val){ 



// cout<<"calc "<
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 "<
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


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<
}

return 0;

}

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

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

U41492 树上数颜色

题意：

题意：

代码：

相关推荐