CF竞赛题目讲解_CF600E(树上启发式合并)
// https://codeforces.com/problemset/problem/600/E
// 与下题类似, DongDong询问以x为根的子树中有多少种不同的颜色.
// https://ac.nowcoder.com/acm/contest/31084/C
#include "stdafx.h"
//#include <bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include <algorithm>
#include <vector>
//#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
//给定树 带点权 询问子树中,出现次数最多的若干种点权的点权和 (颜色值之和)
//暴力解法 对于每个子树都花O(n)求出其答案，并用O(N)清空影响 时间O(N平方)
//发现对于根节点rt,最后递归的子树可以不删,保留信息给根节点,我们最后递归重儿子，保留重儿子的信息 即:启发式合并
//我们保留重儿子，删除轻儿子的影响,并最后重新统计一遍轻儿子
// 某个点u被访问:要么通过重链(不会被删，只会被访问1次),要么通过轻边,但根到u一般logn条轻边，所以 总复杂度nlogn
vector<int> g[maxn];
int v[maxn]={0,
1 ,2, 3, 4
};
int cnt[maxn];
int mmx;//众数出现次数
long long ret, ans[maxn];
int n;
//轻重链剖分
int son[maxn],siz[maxn];
int L[maxn],R[maxn],V[maxn],cur;
void dfs(int rt,int fa) //dfs预处理树上信息
{
siz[rt]=1;// 子树大小
V[L[rt] = cur++] = rt;// 子树dfs编号
for(int &i:g[rt])
{
if(i==fa) continue;
dfs(i,rt);
if(siz[i] > siz[son[rt]]) son[rt]=i;// 求重儿子
siz[rt]+=siz[i];
}
R[rt]=cur;// 子树dfs编号结束位置
}
void add(int rt )// 统计rt贡献
{
cnt[v[rt]]+=1;
if(cnt[v[rt]]==mmx) // 多种颜色同时出现次数最多
{
ret+=v[rt];// 累加颜色值
}
else if(cnt[v[rt]] > mmx) // 一种颜色出现次数最多
{
mmx=cnt[v[rt]];
ret=v[rt];// 重新赋值颜色值
}
//if(rt==2)
{
cout<<"rt="<<rt<<", mmx="<<mmx<<", "<<cnt[v[rt]]<<", "<<ret<<endl;
}
}
void dfs2(int rt,int fa,bool ok) //先递归轻链 最后再求重儿子. 求父节点的答案继承重儿子的信息， 再暴力统计轻儿子
{
for(int &i:g[rt])
{
if(i==fa || i==son[rt]) continue;
dfs2(i,rt,0);
}
if(son[rt]) dfs2(son[rt],rt,1);//重链的信息 不会被删
add(rt); //统计根
for(int &i:g[rt]) //暴力统计轻儿子
{
if(i==fa || i==son[rt]) continue;
for (int k=L[i]; k<R[i]; k++) add(V[k]);
}
ans[rt]=ret;
if(!ok) // 删去整棵轻儿子子树的信息
{
for (int k=L[rt]; k<R[rt]; k++) cnt[v[V[k]]]--;
mmx=-1;
ret=0;
}
}
int edge[32][2]={
1, 2,
2, 3,
2 ,4
};
int main()
{
n=4;
//scanf("%d",&n);
// for(int i=1;i<=n;i++) scanf("%d",v+i);
for(int i=1;i<n;i++)
{
int v,u;
//scanf("%d %d",&u,&v);
u=edge[i-1][0];
v=edge[i-1][1];
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
dfs2(1,0,1);
for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
return 0;
}
