[Codeforces] 600E. Lomsat gelral

題目連結:http://codeforces.com/problemset/problem/600/E

---

詢問子樹區間眾數和，一開始我只想到可以樹壓扁莫隊。後來被雷了之後才知道可以啟發式合併，讓子樹回傳一個map之類的東西記錄每個數字有幾個，而要把子樹們合起來的方式則採用啟發是合併，這樣可以保證每個數字最多被合併$logN$次，要算答案也很簡單，就簡單的看一下現在最大的數字個數有幾個跟維護一下和就好。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
typedef pair<lld,int> PLI;
#define FF first
#define SS second
const int N = 100000 + 5;

int col[N];
lld ans[N];
vector<int> G[N];

PLI dfs(int,int,unordered_map<int,int>&);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>col[i];
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	unordered_map<int,int> mp;
	dfs(1, 1, mp);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
	return 0;
}

PLI dfs(int w, int f, unordered_map<int,int>& res){
	// (res) number -> count
	// (ret) sum, count
	PLI ret = {col[w], 1};
	res[col[w]]=1;
	for(auto i: G[w]){
		if(i==f) continue;
		unordered_map<int,int> tp;
		PLI sub = dfs(i, w, tp);
		if(tp.size() > res.size()){
			swap(tp, res);
			swap(ret, sub);
		}
		for(auto x: tp){
			res[x.FF]+=x.SS;
			if(res[x.FF] > ret.SS) ret = {x.FF, res[x.FF]};
			else if(res[x.FF]==ret.SS) ret.FF += x.FF;
		}
	}
	ans[w] = ret.FF;
	return ret;
}