树上问题都是神仙
又称\(DSU on tree\)
前置芝士
会重链剖分的思想(就是只会口胡就行)
适用范围：我也不知道
理论
就是对每个结点，暴力统计其子树内的信息
只不过在每个结点统计时，继承其重儿子的信息
再来口胡一下复杂度
由于只有轻链会重新统计信息，每个节点到根节点上最多有\(O(logn)\)条轻链
所以总时间复杂度为\(O(nlognf(n)+mf'(n))\)
(\(f(n)\)为单次修改的代价，\(f'(m)\)为单次询问的代价)
例题
Tree and Queries
就是板子，主要是贴个代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int idx,to[N<<1],ne[N<<1],head[N];
int c[N],cnt[N],ccnt[N],ans[N];
int s[N],son[N],f[N],n,m;
inline void add(int x,int y)
{
to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
void dfs(int x,int fa)
{
s[x]=1,f[x]=fa;
for(int i=head[x],y;i;i=ne[i])
{
if((y=to[i])==fa) continue;
dfs(y,x);
s[x]+=s[y];
if(s[y]>s[son[x]]) son[x]=y;
}
}
int d,res;
void add(int x)
{
for(int i=head[x];i;i=ne[i]) if(to[i]!=f[x]) add(to[i]);
ccnt[++cnt[c[x]]]++;
}
void init(int x)
{
--ccnt[cnt[c[x]]--];
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]) init(y);
}
struct node
{
int id,k;
};
vector<node>qu[N];
void solve(int x)
{
if(son[x])
{
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x])
solve(y),init(y),d=0;
solve(son[x]);
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x]) add(y);
}
ccnt[++cnt[c[x]]]++;
for(int i=0;i<qu[x].size();++i) ans[qu[x][i].id]=ccnt[qu[x][i].k];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>c[i];
for(int x,y,i=1;i<n;++i) cin>>x>>y,add(x,y),add(y,x);
for(int x,y,i=1;i<=m;++i) cin>>x>>y,qu[x].push_back((node){i,y});
dfs(1,0);
solve(1);
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
Lomsat gelral
板子
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int idx,to[N<<1],ne[N<<1],head[N];
int c[N],cnt[N],ans[N];
int s[N],son[N],f[N],n;
inline void add(int x,int y)
{
to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
void dfs1(int x,int fa)
{
s[x]=1,f[x]=fa;
for(int i=head[x],y;i;i=ne[i])
{
if((y=to[i])==fa) continue;
dfs1(y,x);
s[x]+=s[y];
if(s[y]>s[son[x]]) son[x]=y;
}
}
int d,res;
void add(int x)
{
for(int i=head[x];i;i=ne[i]) if(to[i]!=f[x]) add(to[i]);
if(++cnt[c[x]]>d)
d=cnt[c[x]],res=c[x];
else if(cnt[c[x]]==d) res+=c[x];
}
void init(int x)
{
--cnt[c[x]];
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]) init(y);
}
void solve(int x)
{
if(son[x])
{
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x])
solve(y),init(y),d=0;
solve(son[x]);
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x]) add(y);
}
if(++cnt[c[x]]>d)
d=cnt[c[x]],res=c[x];
else if(cnt[c[x]]==d) res+=c[x];
ans[x]=res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>c[i];
for(int x,y,i=1;i<n;++i) cin>>x>>y,add(x,y),add(y,x);
dfs1(1,0);
solve(1);
for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
return 0;
}
Dominant Indices
还是板子（所以学会这个就可以水一堆题）,好像用长剖可以做到\(O(n)\)(但我不会)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int idx,to[N<<1],ne[N<<1],head[N];
int c[N],cnt[N],ans[N];
int s[N],son[N],f[N],n;
inline void add(int x,int y)
{
to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
void dfs1(int x,int fa)
{
s[x]=1,f[x]=fa,c[x]=c[fa]+1;
for(int i=head[x],y;i;i=ne[i])
{
if((y=to[i])==fa) continue;
dfs1(y,x);
s[x]+=s[y];
if(s[y]>s[son[x]]) son[x]=y;
}
}
int d,res;
void add(int x)
{
for(int i=head[x];i;i=ne[i]) if(to[i]!=f[x]) add(to[i]);
if(++cnt[c[x]]>d)
d=cnt[c[x]],res=c[x];
else if(cnt[c[x]]==d) res=min(res,c[x]);
}
void init(int x)
{
--cnt[c[x]];
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]) init(y);
}
void solve(int x)
{
if(son[x])
{
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x])
solve(y),init(y),d=0;
solve(son[x]);
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x]) add(y);
}
if(++cnt[c[x]]>d)
d=cnt[c[x]],res=c[x];
else if(cnt[c[x]]==d) res=min(res,c[x]);
ans[x]=res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int x,y,i=1;i<n;++i) cin>>x>>y,add(x,y),add(y,x);
dfs1(1,0);
solve(1);
for(int i=1;i<=n;++i) cout<<ans[i]-c[i]<<endl;
return 0;
}
Blood Cousins Return
还是板子,用\(set\)维护出现的集合，注意数据是森林
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int idx,to[N<<1],ne[N<<1],head[N];
int c[N],ans[N];
int s[N],son[N],f[N],n,m,dep[N];
inline void add(int x,int y)
{
to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
void dfs1(int x,int fa)
{
s[x]=1,f[x]=fa,dep[x]=dep[fa]+1;
for(int i=head[x],y;i;i=ne[i])
{
if((y=to[i])==fa) continue;
dfs1(y,x);
s[x]+=s[y];
if(s[y]>s[son[x]]) son[x]=y;
}
}
int d,res;
set<int>se[N];
void add(int x)
{
for(int i=head[x];i;i=ne[i]) if(to[i]!=f[x]) add(to[i]);
se[dep[x]].insert(c[x]);
}
void init(int x)
{
se[dep[x]].clear();
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]) init(y);
}
struct node
{
int id,k;
};
vector<node>qu[N];
void solve(int x)
{
if(son[x])
{
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x])
solve(y),init(y),d=0;
solve(son[x]);
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x]) add(y);
}
se[dep[x]].insert(c[x]);
for(int i=0;i<qu[x].size();++i) ans[qu[x][i].id]=se[qu[x][i].k+dep[x]].size();
}
int t,rt;
map<string,int>mp;
string name;
int vis[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int x,i=1;i<=n;++i)
{
cin>>name>>x;
if(!x) vis[i]=1;
else add(x,i);
if(!mp[name]) mp[name]=++t;
c[i]=mp[name];
}
cin>>m;
for(int x,y,i=1;i<=m;++i) cin>>x>>y,qu[x].push_back((node){i,y});
for(int i=1;i<=n;++i)
{
if(vis[i])
{
dfs1(i,0);
solve(i);
init(i);
}
}
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
Tree Requests
终于比板子难一点了
由于是回文串，所以出现次数为奇数的种类数只能不超过\(2\)，然后就可做了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int idx,to[N<<1],ne[N<<1],head[N];
int c[N],ans[N],cnt[N][26],ccnt[N];
int s[N],son[N],f[N],n,m,dep[N];
inline void add(int x,int y)
{
to[++idx]=y,ne[idx]=head[x],head[x]=idx;
}
void dfs1(int x,int fa)
{
s[x]=1,f[x]=fa,dep[x]=dep[fa]+1;
for(int i=head[x],y;i;i=ne[i])
{
if((y=to[i])==fa) continue;
dfs1(y,x),s[x]+=s[y];
if(s[y]>s[son[x]]) son[x]=y;
}
}
int d,res;
void add(int x)
{
for(int i=head[x];i;i=ne[i]) if(to[i]!=f[x]) add(to[i]);
if((++cnt[dep[x]][c[x]])&1) ++ccnt[dep[x]];
else --ccnt[dep[x]];
}
void init(int x)
{
if((--cnt[dep[x]][c[x]])&1) ++ccnt[dep[x]];
else --ccnt[dep[x]];
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]) init(y);
}
struct node
{
int id,k;
};
vector<node>qu[N];
void solve(int x)
{
if(son[x])
{
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x])
solve(y),init(y),d=0;
solve(son[x]);
for(int y,i=head[x];i;i=ne[i])
if((y=to[i])!=f[x]&&y!=son[x]) add(y);
}
if((++cnt[dep[x]][c[x]])&1) ++ccnt[dep[x]];
else --ccnt[dep[x]];
for(int i=0;i<qu[x].size();++i) ans[qu[x][i].id]=ccnt[qu[x][i].k];
}
char str[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int x;
for(int i=2;i<=n;++i) cin>>x,add(x,i);
cin>>str+1;
for(int i=1;i<=n;++i) c[i]=str[i]-'a';
for(int x,y,i=1;i<=m;++i) cin>>x>>y,qu[x].push_back((node){i,y});
dfs1(1,0);
solve(1);
for(int i=1;i<=m;++i) puts(ans[i]>1?"No":"Yes");
return 0;
}