題目鏈接：點擊這里
題目大意：
給定一棵以
1
1
1 為根的樹，每個節點都有一個顏色編號，求以每個節點為根的子樹中，顏色出現次數最多的編號之和，（次數最多的可能有多個顏色）
題目分析：
樹啟模板，更新的時候，記錄顏色出現的次數，次數超過或者等于最大值時進行更新即可
具體細節見代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
int res = 0,flag = 1;
char ch = getchar();
while(ch<'0' || ch>'9')
{
if(ch == '-') flag = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
{
res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
ch = getchar();
}
return res*flag;
}
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
vector<int>v[maxn];
int col[maxn],siz[maxn],son[maxn];
ll ans[maxn],cnt[maxn],sum,maxx;
void update(int u,int fa,int val,int heavy)
{
cnt[col[u]] += val;
if(cnt[col[u]] > maxx)
{
sum = col[u];
maxx = cnt[col[u]];
}
else if(cnt[col[u]] == maxx)
sum += col[u];
for(auto it:v[u])
{
if(it == fa || it == heavy) continue;
update(it,u,val,heavy);
}
}
void dfs1(int u,int fa)
{
siz[u] = 1;
for(auto it:v[u])
{
if(it == fa) continue;
dfs1(it,u);
siz[u] += siz[it];
if(siz[it] > siz[son[u]]) son[u] = it;
}
}
void dfs2(int u,int fa,int keep)
{
for(auto it:v[u])
{
if(it == fa || it==son[u]) continue;
dfs2(it,u,0);
}
if(son[u]) dfs2(son[u],u,1);
update(u,fa,1,son[u]);
ans[u] = sum;
if(!keep)
{
update(u,fa,-1,-1);
sum = maxx = 0;
}
}
int main()
{
int n = read();
for(int i = 1;i <= n;++i)
col[i] = read();
for(int i = 1;i < n;i++)
{
int u = read(),v = read();
::v[u].push_back(v);
::v[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0,1);
for(int i = 1;i <= n;i++)
printf("%lld%c",ans[i],i==n?'\n':' ');
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/211298.html
標籤：其他
下一篇：Java寫的第一個小游戲