cf600E. Lomsat gelral

?題意：給出一個樹，求出每個節(jié)點的子樹中出現(xiàn)次數(shù)最多的顏色的編號和

板子題

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int maxn = 100000 + 10 ; struct Node {int to,next; }edge[maxn * 2]; int head[maxn * 2],tot; void add(int x,int y) {edge[++tot].to = y;edge[tot].next = head[x];head[x] = tot; } long long n,col[maxn],siz[maxn],ans[maxn],son[maxn]; void dfs1(int u,int fa) {siz[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]]) son[u]=v;} } long long cnt[maxn],maxx,sum,Son; void add(int u,int fa,int val) {cnt[col[u]]+=val;if(cnt[col[u]] > maxx) maxx = cnt[col[u]] , sum = col[u];else if(cnt[col[u]] == maxx) sum+=col[u];for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(v==fa || v == Son) continue;add(v,u,val);} } void dfs2(int u,int fa,int xp) {for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(v==fa) continue;if(v!=son[u]) dfs2(v,u,0);}if(son[u]) dfs2(son[u],u,1),Son = son[u];add(u,fa,1); Son = 0;ans[u]=sum;if(!xp) add(u,fa,-1) , sum = 0 , maxx = 0 ; } int main() {cin>>n;for(int i=1;i<=n;i++) scanf("%lld",&col[i]);for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}dfs1(1,0);dfs2(1,0,0);for(int i=1;i<=n;i++) printf("%lld ",ans[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hfang/p/11486503.html

總結(jié)

以上是生活随笔為你收集整理的Lomsat gelral的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。