网站建设服务费税率多少,WordPress文档批量发布接口,网站建设林晓东,seo关键词排名优化方案cf600 E. Lomsat gelral
题意#xff1a;
给出一个树#xff0c;求出每个节点的子树中出现次数最多的颜色的编号和
题解#xff1a;
树上启发式合并 树上启发式合并讲解 其实就是#xff1a;递归轻儿子#xff0c;消除影响#xff0c;递归重儿子#xff0c;不消除影…cf600 E. Lomsat gelral
题意
给出一个树求出每个节点的子树中出现次数最多的颜色的编号和
题解
树上启发式合并 树上启发式合并讲解 其实就是递归轻儿子消除影响递归重儿子不消除影响递归轻儿子
void Dsu(int x,int fa,int opt){for(all Edge){if(to!fato!BigSon[x])//暴力统计轻边的贡献dfs(to,x,0);}if(son[x])dfs(BigSon[x],x,1);//统计重儿子的贡献不消除影响add(x);//暴力统计所有轻儿子的贡献ans[x]NowAns;//更新答案if(!opt)delet(x);//删除刚开始统计轻边的影响
}代码
// Problem: E. Lomsat gelral
// Contest: Codeforces - Educational Codeforces Round 2
// URL: https://codeforces.com/contest/600/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Data:2021-08-18 23:54:38
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 3e5 9;
int n;
ll col[maxn];
int son[maxn], siz[maxn], cnt[maxn];
int Mx, Son;
ll sum, ans[maxn];
vectorint vec[maxn];
void dfs1(int u, int fa)
{siz[u] 1;for (auto it : vec[u]) {int v it;if (v fa)continue;dfs1(v, u);siz[u] siz[v];if (siz[v] siz[son[u]])son[u] v; //轻重链剖分}
}
void add(int x, int fa, int val)
{cnt[col[x]] val; //计算贡献if (cnt[col[x]] Mx) {Mx cnt[col[x]];sum col[x];}else if (cnt[col[x]] Mx) {sum col[x];}for (auto it : vec[x]) {int v it;if (v fa || v Son)continue; //v是重儿子continueadd(v, x, val); //继续统计}
}
void dfs2(int u, int fa, int opt)
{for (auto it : vec[u]) {int v it;if (v ! fa v ! son[u]) //说明是轻边dfs2(v, u, 0);}if (son[u]) {dfs2(son[u], u, 1); //统计重儿子的贡献Son son[u];}add(u, fa, 1); //暴力统计所有轻儿子的贡献Son 0;ans[u] sum;if (!opt) {add(u, fa, -1); //消除贡献sum 0;Mx 0;}
}
int main()
{//rd_test();read(n);for (int i 1; i n; i)read(col[i]);for (int i 1; i n; i) {int x, y;read(x, y);vec[x].push_back(y);vec[y].push_back(x);}dfs1(1, 0); //重链剖分dfs2(1, 0, 0);for (int i 1; i n; i) {printf(%lld , ans[i]);}return 0;//Time_test();
}
