codeforces 660E Lomsat gelral

2019-11-08 18:36:06

字體：大中小

供稿：網(wǎng)友

題目鏈接

分析：

這是一道啟發(fā)式合并的題目，大致思路非常簡單，就是從根節(jié)點dfs，對于每棵子樹，將它子節(jié)點的信息合并到子樹根節(jié)點。合并的過程中，把小樹合并到大樹中降低復(fù)雜度?？梢岳胢ap, s[i][j][k] $s[i][j][k]$ 指以i $i$ 為根節(jié)點的子樹中，顏色j $j$ 的節(jié)點數(shù)量。cnt[i] $cnt[i]$ 記錄節(jié)點i $i$ 的答案。

存疑：

我自己只是大致明白f $f$ 數(shù)組的作用，但是具體究竟是怎么實現(xiàn)的，現(xiàn)在還需要留一個疑問，待以后自己熟練了再來解決這個疑問吧。。。

代碼：

/*****************************************************///#PRagma comment(linker, "/STACK:1024000000,1024000000")#include <map>#include <set>#include <stack>#include <queue>#include <cmath>#include <string>#include <vector>#include <cstdio>#include <cstring>#include <sstream>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define offcin ios::sync_with_stdio(false)#define DEBUG freopen("#.txt", "r", stdin)#define sigma_size 26#define lson l,m,v<<1#define rson m+1,r,v<<1|1#define slch v<<1#define srch v<<1|1#define ll long long#define ull unsigned long long#define lowbit(x) (x&-x)const int INF = 0x3f3f3f3f;const ll INFF = 1e18;const double pi = acos(-1.0);const double inf = 1e18;const double eps = 1e-9;const ll mod = 1e9+7;const int maxmat = 10;const ull BASE = 133333331;/*****************************************************/inline void RI(int &x) { char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';}inline int bits(ll x) { return !x ? x : bits(x - lowbit(x)) + 1;}/*****************************************************/const int maxn = 1e5 + 5;std::vector<int> G[maxn];std::map<int, ll> s[maxn];int f[maxn], c[maxn], m[maxn];ll cnt[maxn], ans[maxn];void unite(int a, int b) { if (s[f[a]].size() > s[f[b]].size()) swap(f[a], f[b]); for (auto x : s[f[a]]) { s[f[b]][x.first] += x.second; if (s[f[b]][x.first] > m[f[b]]) { m[f[b]] = s[f[b]][x.first]; cnt[f[b]] = 0; } if (m[f[b]] == s[f[b]][x.first]) cnt[f[b]] += x.first; }}void dfs(int u, int fa) { for (int v : G[u]) if (v != fa) { dfs(v, u); unite(v, u); } ans[u] = cnt[f[u]];}int main(int argc, char const *argv[]) { int N; cin>>N; for (int i = 1; i <= N; i ++) { cin>>c[i]; f[i] = i; s[i][c[i]] = 1; cnt[i] = c[i]; m[i] = 1; } for (int i = 1; i < N; i ++) { int u, v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1, -1); for (int i = 1; i <= N; i ++) cout<<ans[i]<<" "; return 0;}

上一篇：深入剖析Spring(二)——IoC容器的實現(xiàn)

下一篇：深入剖析Spring(一)——IoC的基本概念(從面向?qū)ο蠼嵌冉榻B)