[Codeforces] 600E. Lomsat gelral
題目連結:http://codeforces.com/problemset/problem/600/E
詢問子樹區間眾數和,一開始我只想到可以樹壓扁莫隊。後來被雷了之後才知道可以啟發式合併,讓子樹回傳一個map之類的東西記錄每個數字有幾個,而要把子樹們合起來的方式則採用啟發是合併,這樣可以保證每個數字最多被合併$logN$次,要算答案也很簡單,就簡單的看一下現在最大的數字個數有幾個跟維護一下和就好。
詢問子樹區間眾數和,一開始我只想到可以樹壓扁莫隊。後來被雷了之後才知道可以啟發式合併,讓子樹回傳一個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;
}
留言
張貼留言