題目鏈接：點擊查看

題目大意：給出一棵樹，每個節(jié)點都有一個編號代表一種顏色，現在對于每個子樹求出現最多的顏色的編號之和

題目分析：因為n給到了1e5，看完這個題第一反應就是暴力n*n，但顯然是會超時的，既然是在樹上那么考慮用樹鏈剖分+線段樹優(yōu)化，可還不是最優(yōu)解，用樹上莫隊也不太行，莫隊會帶著一個根號，我們需要帶著log，于是就學習了一波樹上啟發(fā)式合并，時間復雜度只有nlogn，原理就是利用子樹上的信息更新祖先的信息，而不用每次都重新計算了，為了可以順利的更新，我們先用樹鏈剖分的思想拿出重鏈，在維護信息的時候只保存重鏈上的信息即可，對于輕鏈上的信息我們用完就舍棄掉即可，本著先跑輕鏈再跑重鏈最后再跑輕鏈的原則，這樣能保證最后跑完的信息恰好是子樹的信息，且將長度較小的輕鏈合并到長度較長的重鏈上去，即實現了啟發(fā)式合并，樹鏈剖分限制了這個操作在logn的時間復雜度內，所以總的時間復雜度為nlogn，對于這個題目而言就是一個模板題了，具體的實現看代碼吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int color[N],num[N],son[N],cnt[N];LL ans[N],sum,mmax;bool vis[N];vector<int>node[N];void dfs_son(int u,int fa)//樹鏈剖分跑出重鏈 {son[u]=-1;num[u]=1;for(auto v:node[u]){if(v==fa)continue;dfs_son(v,u);num[u]+=num[v];if(son[u]==-1||num[v]>num[son[u]])son[u]=v;} }void cal(int u,int fa,int val)//對于每個節(jié)點計算其子樹的貢獻 {cnt[color[u]]+=val;if(val>0&&cnt[color[u]]>=mmax){if(cnt[color[u]]>mmax){sum=0;mmax=cnt[color[u]];}sum+=color[u];}for(auto v:node[u]){if(v==fa||vis[v])continue;cal(v,u,val);} }void dfs(int u,int fa,int keep)//啟發(fā)式合并 {for(auto v:node[u]){if(v==fa||v==son[u])continue;dfs(v,u,0);}if(son[u]!=-1){dfs(son[u],u,1);vis[son[u]]=true;}cal(u,fa,1);ans[u]=sum;if(son[u]!=-1)vis[son[u]]=false;if(!keep){cal(u,fa,-1);sum=mmax=0;} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",color+i);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs_son(1,-1);dfs(1,-1,1);for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 600E Lomsat gelral(树上启发式合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。