codeforces 660E Lomsat gelral

2019-11-08 18:36:06

字体：大中小

来源：转载

供稿：网友

题目链接

分析：

这是一道启发式合并的题目，大致思路非常简单，就是从根节点dfs，对于每棵子树，将它子节点的信息合并到子树根节点。合并的过程中，把小树合并到大树中降低复杂度。可以利用map, s[i][j][k] $s[i][j][k]$ 指以i $i$ 为根节点的子树中，颜色j $j$ 的节点数量。cnt[i] $cnt[i]$ 记录节点i $i$ 的答案。

存疑：

我自己只是大致明白f $f$ 数组的作用，但是具体究竟是怎么实现的，现在还需要留一个疑问，待以后自己熟练了再来解决这个疑问吧。。。

代码：

/*****************************************************///#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容器的实现

下一篇：深入剖析Spring(一)——IoC的基本概念(从面向对象角度介绍)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注