[蓝桥杯 2023 省 A] 颜色平衡树

1. 暴力做法 70分

#include
using namespace std;const int N=2e5+10;int h[N],e[N],ne[N],idx;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int n,clo[N],cnt[N],ccnt[N],sz[N],son[N];
int ans;int dfs_son(int u){sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];int v=dfs_son(j);sz[u]+=v;if(sz[son[u]]1) add(f,i);}dfs_son(1);dfs(1,1); printf("%d\n",ans);return 0;
}

2. 启发式合并

#include
using namespace std;const int N=2e5+10;int h[N],e[N],ne[N],idx;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int n,clo[N],cnt[N],ccnt[N],sz[N],son[N];
int ans;int dfs_son(int u){sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];int v=dfs_son(j);sz[u]+=v;if(sz[son[u]]1) add(f,i);}dfs_son(1);dfs(1,1); printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！