2022.03.11 点分树
2022.03.11 点分树
2.1 前置知识
2.1.1 点分治
点分治是每次选择子树中的重心不断更新答案的东西。
对于父节点x和子节点y，\(dis(x,y)=k\)，可以先以x为子树中的根节点计算出除它自己外子树中任意两个节点u、v的dis。不过如果u、v的lca是y，那么相当于多计算了两遍从x到y，对此减去……抱歉，我还不会。
可以参考
https://blog.csdn.net/qq_39553725/article/details/77542223
2.2 点分树
2.2.1 点分树
把每次分治的重心连起来，就是一颗树。这棵树叫点分树。
因为是重心，所以树高不超过\(logn\)。一个新树上的子树表示它原本树上的连通块。所以原树上任意两点x、y在新树上的lca在原树上x到y的路径上，即\(dis(x,y)=dis(x,lca)+dis(lca,y)\)。
2.2.2 P6329 【模板】点分树 | 震波（点分树模板）
https://www.luogu.com.cn/problem/P6329
//https://www.luogu.com.cn/blog/SHEEP-BOLG/post-ti-xie-p6329-mu-ban-dian-fen-shu-zhen-bo
#include
using namespace std;
const int N=2e5+10;
int n,m,cnt,head[N],val[N],root,sizei[N],maxn[N],vis[N];
int tot,ind,fa[N],dep[N],true_id[N],f[N<<1][21],logi[N<<1];
struct node{
int to,next;
}a[N<<1];
vectort[2][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void pre(int x,int fai){
f[++ind][0]=x;true_id[x]=ind;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai)continue;
dep[v]=dep[x]+1;
pre(v,x);
f[++ind][0]=x;
}
}
inline int depmin(int x,int y){
return dep[x]true_id[y])swap(x,y);
int xi=true_id[x],yi=true_id[y];
int k=logi[yi-xi+1];
int lca=depmin(f[xi][k],f[yi-(1<=u)lasti+=query(0,fa[i],y-u)-query(1,i,y-u);
//这里请参考eleveni的神奇想法：
//宝石那题一层一层往上蹦着记录fa[i]对答案的贡献
//减去fa[i]已经被计算过的子树的贡献
}
cout< 2.2.3 P6626 [省选联考 2020 B 卷] 消息传递(简化版模板)
https://www.luogu.com.cn/problem/P6626
30pts：暴力+线段树
我执意要把一个父亲一个父亲蹦的代码搞上来，然后它TLE了……
#include
using namespace std;
const int N=1e5+10;
int T,n,m,cnt,head[N],dep[N],ans;
struct node{
int to,next;
}a[N<<1];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs(int x,int fai,int k){
dep[x]=dep[fai]+1;
if(dep[x]==k)++ans;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai)continue;
dfs(v,x,k);
}
}
inline void solve1(){
for(int i=1;i<=m;i++){
ans=0;
int x,k;
x=read();k=read();
dfs(x,0,k+1);
cout<>1;
build(lson(x),l,mid);
build(rson(x),mid+1,r);
update(x);
}
inline int query(int x,int l,int r,int L,int R,int k){
if(l==r)return t[x].val==k;
if(l>=L&&r<=R){
if(t[x].valR)return 0;
int mid=(l+r)>>1;
int fin=0;
if(L<=mid)fin+=query(lson(x),l,mid,L,R,k);
if(R>mid)fin+=query(rson(x),mid+1,r,L,R,k);
return fin;
}
inline void dfs2(int x,int fai){
dep[x]=dep[fai]+1;
fa[x]=fai;
sizei[x]=1;
id_true[++ind]=x;
true_id[x]=ind;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai)continue;
dfs2(v,x);
sizei[x]+=sizei[v];
}
}
inline void find(){
cout<<"tree "<=v+1)ans+=query(1,1,ind,v+1,vi,k);
u=ui,v=vi;
}
cout< 100pts：点分树
好家伙，连修改都不用，直接上来怼！
#include
using namespace std;
const int N=1e5+10;
int n,T,m,cnt,head[N],dep[N];
int tot,root,sizei[N],maxn[N],vis[N];
int fa[N],ind,f[N<<1][21],true_id[N],logi[N<<1];
struct node{
int to,next;
}a[N<<1];
vectort[2][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void pre(int x,int fai){
dep[x]=dep[fai]+1;
f[++ind][0]=x;
true_id[x]=ind;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai)continue;
pre(v,x);
f[++ind][0]=x;
}
}
inline void height(int x,int fai){
sizei[x]=1;maxn[x]=0;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai||vis[v])continue;
height(v,x);
sizei[x]+=sizei[v];
maxn[x]=max(maxn[x],sizei[v]);
}
maxn[x]=max(maxn[x],tot-sizei[x]);
if(maxn[x]true_id[y])swap(x,y);
int xi=true_id[x],yi=true_id[y];
int k=logi[yi-xi+1];
int lca=depmin(f[xi][k],f[yi-(1<=k)fin=t[0][x][k];
for(int i=x;fa[i];i=fa[i]){
int disi=Dis(x,fa[i]);
if(disi>k||(k-disi)>sizei[fa[i]])continue;
fin+=t[0][fa[i]][k-disi];
if(sizei[i]>=k-disi)fin-=t[1][i][k-disi];
}
return fin;
}
inline void init(){
memset(true_id,0,sizeof(true_id));
memset(sizei,0,sizeof(sizei));
memset(head,0,sizeof(head));
memset(maxn,0,sizeof(maxn));
memset(dep,0,sizeof(dep));
memset(vis,0,sizeof(vis));
memset(fa,0,sizeof(fa));
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
t[0][i].erase(t[0][i].begin(),t[0][i].end()),
t[1][i].erase(t[1][i].begin(),t[1][i].end());
cnt=ind=tot=0;
}
signed main(){
T=read();
while(T--){
init();
n=read();m=read();
for(int i=1;i