dsu on tree
树上启发式合并
一般解决下列特征的题目：
1．询问子树的某些信息
2．没有修改操作
codeforces 600 E. Lomsat gelral
Problem Description
一棵树有n个结点的有根数，每个结点都有一种颜色，每个颜色有一个编号，求树中每个节点的子树中最多的颜色编号的和。
Analysis of ideas
首先将树进行轻重链剖分，处理出每个节点的重儿子
然后对于树上的询问，如果是重儿子，则暴力统计他的贡献，保留其贡献，轻儿子则在统计完他的贡献后消除其贡献
这里说的保留和消除是指的节点整个子树的贡献
举个栗子，上面这幅图中
我们先跳到２号节点，然后发现２号还有轻儿子，然后跳到５号节点，统计其信息，因为５号是轻儿子，然后消除它的贡献
然后２号还有重儿子．．．（dfs），之后到达１２号节点，统计，消除
然后是１１号节点，统计，保留，
回溯到６号节点，暴力统计它的轻儿子，也就是去搜６，１２号节点，保留
回溯到２号节点，暴力统计它的轻儿子，也就是去搜２，５号节点，因为２是轻儿子，所以消除
重复这个过程
Accepted code
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 101110;
const int M = 1e9+7;
int n,m,k,ok;
vector<int> v[maxn]; //图
int sz[maxn],son[maxn]; //i号节点子树的大小,i号节点的儿子
int col[maxn]; //i节点的颜色
int cnt[maxn]; //i号颜色的个数
int ans[maxn];
int sum,mx; //最多编号颜色的和,最多编号个数
int Son;
void dfs(int u,int pre) //轻重链剖分
{
sz[u] = 1;
for(auto i : v[u])
{
if(i == pre) continue;
dfs(i,u);
sz[u] += sz[i];
if(sz[i] > sz[son[u]]) son[u] = i;
}
}
void add(int u,int pre,int val) //给u的子树加上val
{
cnt[col[u]]+=val;
if(cnt[col[u]] > mx)
{
sum = col[u];
mx = cnt[col[u]];
}
else if(cnt[col[u]] == mx)
{
sum += col[u];
}
for(auto i : v[u])
{
if(i == pre || i == Son) continue;
add(i,u,val);
}
}
//加的时候不考虑重儿子,删的时候考虑重儿子
void dfs2(int u,int pre,int opt) //opt=0表示结束后消除影响
{
for(auto i : v[u])
{
if(i == pre || i == son[u]) continue;
dfs2(i,u,0); //先搜轻儿子
}
if(son[u]) dfs2(son[u],u,1),Son = son[u]; //再搜重儿子,记录重儿子
add(u,pre,1); //暴力搜u的轻儿子
Son = 0; //接下来要删除,不考虑轻重儿子
ans[u] = sum;
if(!opt) add(u,pre,-1),mx = 0,sum = 0; //消除影响
}
signed main()
{
#ifdef ONLINE_JUDGE
#else
freopen("data.in", "r", stdin);
#endif
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>col[i];
}
for(int i = 1,x,y; i < n; i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
dfs2(1,0,1);
for(int i = 1; i <= n; i++)
{
cout<<ans[i]<<' ';
}
cout<<endl;
return 0;
}