题意
给一颗有根树,节点有颜色,求每个点子树内出现次数最多的颜色的权值(有多个就是权值和)。
1 ≤ n ≤ 105
1 ≤ ci ≤ n 权值
题解
考虑暴力的做法,对于每个节点直接遍历,将颜色放入桶,统计答案。这样复杂度是n2的。
怎么去优化呢?可以看到每次遍历完一棵子树,我们都是把桶清空再重新遍历,其实他的有些信息是可以保留的。
如何就出现了一种做法,对于整个树先dfs一遍找出每个点的重儿子(同树链剖分)
我们再遍历时,从根遍历,先进轻儿子所在子树,统计轻儿子的答案,然后将桶清除。
然后再进重儿子所在子树,统计重儿子答案,不清除桶。
接着再把轻儿子和他本身加入桶,统计答案。
看上去也很暴力,那为什么时间复杂度是对的呢?
遇到一条轻边,就会把整个子树加入一遍,对于每个点,他到根的轻边条数就是他被加入的次数,所以复杂度nlgn
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=100005; int n; int co[maxn]; int size[maxn],fa[maxn],son[maxn]; ll get_it[maxn],ans; int cx[maxn],num; vector<int>e[maxn]; void dfs(int u){ size[u]=1; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]) continue; fa[v]=u; dfs(v); size[u]+=size[v]; if(size[son[u]]<size[v]) son[u]=v; } } void clear(int u){ cx[co[u]]--; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]) continue; clear(v); } } void add(int u){ cx[co[u]]++; if(cx[co[u]]>num) ans=co[u],num=cx[co[u]]; else if(cx[co[u]]==num) ans+=co[u]; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]) continue; add(v); } } void get_ans(int u){ if(!u) return ; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==fa[u]||v==son[u]) continue; get_ans(v); ans=0;num=0; clear(v); //for(int i=1;i<=n;i++) printf("%d ",cx[i]); //putchar(10); } get_ans(son[u]); for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(v==son[u]||v==fa[u]) continue; add(v); } cx[co[u]]++; if(cx[co[u]]>num) ans=co[u],num=cx[co[u]]; else if(cx[co[u]]==num) ans+=co[u]; get_it[u]=ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&co[i]); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); e[x].push_back(y); e[y].push_back(x); } dfs(1); get_ans(1); for(int i=1;i<=n;i++) printf("%I64d ",get_it[i]); }View Code