树上合并
-
总的来说，树上合并类问题主要用于解决树上统计种类数、最大值一类的问题。
-
最朴素的树上合并思路为分别统计每个子树的答案合并再加上父亲节点本身的答案。一般采用启发式合并，将小子树合并进大子树中
如
树上数颜色
- 题意：
给定一颗有根树，每个节点有颜色，求每棵子树的颜色种类数 - 简要题解：
非常经典，颜色数统计用类似莫队的桶，每到加到临界点便改变颜色数，运用类似树剖的思想，将dfn序与重儿子预处理出来启发式合并优化复杂度
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector <int> q[N];
int n,tot[N],c[N],dfn[N],colordfn,siz[N],big[N],L[N],R[N],cnt[N],ans[N],ques[N];
void add(int i)
{
if(cnt[c[i]]==0) colordfn++;
cnt[c[i]]++;
}
void del(int i)
{
cnt[c[i]]--;
if(cnt[c[i]]==0) colordfn--;
}
void dfs0(int u,int fa)//初始化dfn序和树的相关信息
{
L[u]=++colordfn;dfn[colordfn]=u;siz[u]=1;//L->u在dfn序中的位置 dfn->dfn序
for(int i=0;i<tot[u];i++)
{
int v=q[u][i];
if(v==fa) continue;
dfs0(v,u);
siz[u]+=siz[v];
if(!big[u]||siz[v]>siz[big[u]]) big[u]=v;//处理重儿子
}
R[u]=colordfn;
}
void dfs1(int u,int fa,bool keep)
{
for(int i=0;i<tot[u];i++)
{
int v=q[u][i];
if(v==big[u]||v==fa) continue;
dfs1(v,u,0);
}
if(big[u])
dfs1(big[u],u,1);
for(int i=0;i<tot[u];i++)
{
int v=q[u][i];
if(v==fa||v==big[u]) continue;
for(int i=L[v];i<=R[v];i++)
add(dfn[i]);
}
add(u);
ans[u]=colordfn;
if(keep==0)
for(int i=L[u];i<=R[u];i++)
del(dfn[i]);
}
int main()
{
cin>>n;
for(int i=1,u,v;i<n;i++)
{
cin>>u>>v;
q[u].push_back(v),tot[u]++;
q[v].push_back(u),tot[v]++;
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
dfs0(1,0);
colordfn=0;
dfs1(1,0,0);
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>ques[i];
}
for(int i=1;i<=m;i++) cout<<ans[ques[i]]<<endl;
return 0;
}
线段树合并
- 题意：给定一棵树，给定一段从u到v的简单路径，给这条简单路径上的所有点发放一个权值，求每个点最后拥有最多的是哪种权值
- 题解：经典的树上区间加求种类数问题。区间操作考虑树上差分，操作为u+1,v+1,lca(u,v)-1,fa[lca(u,v)]-1。差分后求种类数要将子树的答案和这个节点自己的答案合并。直接用桶按位合并是\(O({n^2)}\) 的，于是考虑对每个结点建一颗线段树，统计答案时一层一层向上合并。
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
const int M=1e5+10;
const int LOG=20;
const int rmax=100000;
int f[M][LOG+10],dep[M],rt[M],sum[N],ls[N],rs[N],res[N],n,m,cnt,tot[M],ans[M];
vector <int> q[M];
void initlca(int u,int fa) //初始化倍增函数f
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<LOG;i++) f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<tot[u];i++)
{
int v=q[u][i];
if(v==fa) continue;
initlca(v,u);
}
}
int lca(int a,int b) //求lca
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=LOG-1;i>=0;i--)
if(dep[f[a][i]]>=dep[b]) a=f[a][i];
if(a==b) return a;
for(int i=LOG;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
return f[a][0];
}
void push_up(int id)
{
if(sum[ls[id]]<sum[rs[id]])
{
sum[id]=sum[rs[id]];
res[id]=res[rs[id]];
}
else
{
sum[id]=sum[ls[id]];
res[id]=res[ls[id]];
}
}
int build(int id,int l,int r,int color,int val) //新建节点
{
if(!id) id=++cnt;
if(l==r)
{
sum[id]+=val,res[id]=color;
return id;
}
int mid=(l+r)>>1;
if(color<=mid) ls[id]=build(ls[id],l,mid,color,val);
else rs[id]=build(rs[id],mid+1,r,color,val);
push_up(id);
return id;
}
int merge(int a,int b,int l,int r)
{
if(!a||!b) return a+b;
if(l==r)
{
sum[a]+=sum[b];
return a;
}
int mid=(l+r)>>1;
ls[a]=merge(ls[a],ls[b],l,mid);
rs[a]=merge(rs[a],rs[b],mid+1,r);
push_up(a);
return a;
}
void cacl(int u)
{
for(int i=0;i<tot[u];i++)
{
int v=q[u][i];
if(v==f[u][0]) continue;
cacl(v);
rt[u]=merge(rt[u],rt[v],1,rmax);
}
ans[u]=res[rt[u]];
if(sum[rt[u]]==0) ans[u]=0;
}
int main()
{
cin>>n>>m;
for(int i=1,u,v;i<n;i++)
{
cin>>u>>v;
q[u].push_back(v),tot[u]++;
q[v].push_back(u),tot[v]++;
}
initlca(1,0);
for(int i=1,x,y,z;i<=m;i++)
{
cin>>x>>y>>z;
rt[x]=build(rt[x],1,rmax,z,1);
rt[y]=build(rt[y],1,rmax,z,1);
int l=lca(x,y);
rt[l]=build(rt[l],1,rmax,z,-1);
rt[f[l][0]]=build(rt[f[l][0]],1,rmax,z,-1);
}
cacl(1);
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}