脚本宝典收集整理的这篇文章主要介绍了dsu on tree学习笔记，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
可以用来处理一些树上的问题，一般有2个特征：
考虑暴力做法，对于每个子树，遍历一遍求答案，@R_148_1304@是 (O(n^2)) 的。
但是其实在求当前子树的答案时，它的信息父亲也是要用的，但是我们不能全继承上去，因为在遍历它的儿子求答案时，是相互独立的，需要清空。所以我们考虑怎么样能使优化最大化，显然是继承重儿子。
重儿子的预处理就是轻重链剖分。
因此，先遍历所有轻儿子，统计完答案后清空，再遍历重儿子，统计答案，继承给父亲。
类似于树剖，因为重儿子继承了，所以是 (O(nLOG n))。
Link
题意：
给出一个树，求出每个节点的子树中出现次数最多的颜色的编号和。
板子题，开个数组记录一下每个颜色的个数，暴力统计即可。
#include <iostream>
#include <cstdio>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, c[N];
vector <int> g[N];
int siz[N], son[N];
void DFs1(int u, int fa)
{
siz[u] = 1;
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
int Son, mx, cnt[N];
ll sum, ans[N];
void add(int u, int fa, int val)
{
cnt[c[u]] += val;
if(cnt[c[u]] > mx) mx = cnt[c[u]], sum = c[u];
else if(cnt[c[u]] == mx) sum += c[u];
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == fa || v == Son) continue;
add(v, u, val);
}
}
void dfs2(int u, int fa, int op)
{
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == fa || v == son[u]) continue;
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(!op) add(u, fa, -1), mx = 0, sum = 0;
}
int rd()
{
int x = 0;
char c = getchar();
while(!isdigIT(c)) c = getchar();
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
return x;
}
int main()
{
n = rd();
for(int i = 1; i <= n; i++)
c[i] = rd();
for(int i = 1; i < n; i++)
{
int u = rd(), v = rd();
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0, 0);
for(int i = 1; i <= n; i++)
PRintf("%lld ", ans[i]);
puts("");
return 0;
}
Link
题意：
给定一颗树，多次询问一颗子树中出现次数 ≥k 的颜色有多少种。
与上一道题类似，但要离线。
先把询问处理一下，把每个子树的询问挂到根上，统计答案时一起算。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
template <tyPEname T>
void read(T &x)
{
x = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
return;
}
template <typename T>
void write(T x)
{
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, col[N];
vector <int> g[N];
struct query
{
int k, id;
};
vector <query> q[N];
int siz[N], son[N], f[N];
void dfs1(int u, int fa)
{
f[u] = fa;
siz[u] = 1;
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
int cnt[N], sum, ans[N], d[N];
void add(int u, int val, int Son)
{
cnt[col[u]] += val;
if(val == 1) d[cnt[col[u]]]++;
else d[cnt[col[u]] + 1]--;
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == f[u] || v == Son) continue;
add(v, val, Son);
}
}
void dfs2(int u, int op)
{
for(int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if(v == f[u] || v == son[u]) continue;
dfs2(v, 0);
}
if(son[u]) dfs2(son[u], 1);
add(u, 1, son[u]);
for(int i = 0; i < q[u].size(); i++)
ans[q[u][i].id] = d[q[u][i].k];
if(!op) add(u, -1, 0), sum = 0;
}
int main()
{
read(n), read(m);
for(int i = 1; i <= n; i++)
read(col[i]);
for(int i = 1, u, v; i < n; i++)
{
read(u), read(v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1, u; i <= m; i++)
{
query t;
read(u), read(t.k);
t.id = i;
q[u].push_back(t);
}
dfs1(1, 0);
dfs2(1, 0);
for(int i = 1; i <= m; i++)
write(ans[i]), puts("");
return 0;
}
dsu on tree入门
以上是脚本宝典为你收集整理的dsu on tree学习笔记全部内容，希望文章能够帮你解决dsu on tree学习笔记所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。