给出一棵以 \(1\) 为根的有 \(n\) 个节点的树，节点 \(i\) 的颜色为 \(c_i\) .
如果一种颜色 \(c\) 在子树 \(i\) 中出现次数最多，则称 \(c\) 在子树 \(i\) 中占有主导地位 .
节点 \(1\) 到 \(n\) ，对于每个节点求出占有主导地位的颜色编号和 .
\(1\leq n\leq 10^5,1\leq c_i\leq n,1\leq x_i,y_i\leq n\)
看到树，想到线段树上区间和启发式合并.
但是，本题以节点为叶子，如果对于一个区间维护颜色最大出现次数和主导地位颜色编号和，是无法 \(O(1)\) 地计算的 .
此时，想到可以考虑启发式合并，按照颜色为叶子建立线段树，维护与一个区间最大出现次数和主导地位颜色编号和 ，这样就容易 \(O(1)\) 地计算了.
那么，如何合并两个线段树，emmm，可能跟线段树合并有关，但是我不会啊……
这就不可以做了吗？怎么可能 . 联想到轻重链剖分，其中必定是 size 小的子树向 size 最大的子树合并. 所以，只有 size 最大的子树建出的线段树在当前计算中是有用的，其他的树根本不用递归下去，是一个独立的子问题.
此时，可以考虑用一个 queue 维护需要处理的子问题，然后，dfs 之前提前计算出线段树的大小 ，再 dfs 递归，启发式合并，递归 size 最大的点，其余小的点为子问题，放入 queue 中，size 小的子树中的点一个一个加入线段树 . 最后，取出线段树的 \(1\) 号节点的主导地位颜色编号和，就是答案了. 要注意标号和要用 long long 存. 我估计只有我一个人这样写的这么奇葩.
时间复杂度 : \(O(nlog^2n)\)
空间复杂度 : \(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
int n;
int c[100010];
vector<int>g[100010];
int L[100010],R[100010],id[100010],pos[100010],cnt=0;
void get_id(int x,int fa){
id[x]=cnt++;
pos[id[x]]=x;
L[x]=R[x]=id[x];
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa)continue;
get_id(to,x);
L[x]=min(L[x],L[to]);
R[x]=max(R[x],R[to]);
}
}
int sz[100010],par[100010];
void get_sz(int x,int fa){
par[x]=fa;sz[x]=1;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa)continue;
get_sz(to,x);
sz[x]+=sz[to];
}
}
bool heavy[100010];
class node{public:int val;long long sum;};
unordered_map<int,int>Map;
node tree[100010*4];
queue<int>Q;
void up(node &x,node l,node r){
if(l.val!=r.val){
if(l.val>r.val)x=l;
else x=r;
}
else{
x.val=l.val;
x.sum=l.sum+r.sum;
}
}
void init(int x,int l,int r,int pos,int val){
if(l==r){
tree[x]=(node){0,val};
return;
}
int mid=(l+r)>>1;
if(pos<=mid)init(x<<1,l,mid,pos,val);
else init(x<<1|1,mid+1,r,pos,val);
up(tree[x],tree[x<<1],tree[x<<1|1]);
}
void upd(int x,int l,int r,int pos,int val){
if(l==r){
tree[x].val++;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(x<<1,l,mid,pos,val);
else upd(x<<1|1,mid+1,r,pos,val);
up(tree[x],tree[x<<1],tree[x<<1|1]);
}
long long ans[100010];
void dfs(int x,int fa){
int Id=-1;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa)continue;
if(Id==-1||sz[Id]<sz[to])Id=to;
}
if(Id!=-1){
dfs(Id,x);
}
upd(1,0,cnt-1,Map[c[x]],1);
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa||to==Id)continue;
for(int j=L[to];j<=R[to];j++){
int y=pos[j];
upd(1,0,cnt-1,Map[c[y]],1);
}
Q.push(to);
}
ans[x]=tree[1].sum;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++)cin>>c[i];
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
u--;v--;
g[u].push_back(v);
g[v].push_back(u);
}
get_id(0,-1);
get_sz(0,-1);
Q.push(0);
while(!Q.empty()){
int x=Q.front();Q.pop();
cnt=0;Map.clear();
for(int i=L[x];i<=R[x];i++){
int y=pos[i];
if(Map.find(c[y])==Map.end())Map[c[y]]=cnt++;
}
for(unordered_map<int,int>::iterator it=Map.begin();it!=Map.end();it++)
init(1,0,cnt-1,it->second,it->first);
dfs(x,par[x]);
}
for(int i=0;i<n;i++)cout<<ans[i]<<" ";
cout<<"\n";
return 0;
}