20230626-树链剖分+点分治-526互联

20230626

重链剖分

计算每个节点子树大小，判断出每个点的重儿子
优先遍历重儿子连边，并且按照 DFS 序重新编号

特点：

每条重链上的点编号是连续的
每个点为根的子树内所有点的编号是连续的 $ \to $线段树

需求：

对于树上两点 $x,y$ 路径上的所有点进行操作
必然不能避免的事情就是 LCA，寻找最近公共祖先
按照每条链上跳，跳的时候顺便处理掉这段区间的值
对于树上两点 $x,y$ 路径上的所有点求和，根上述操作一致
对于树上某个点 $x$ 为根的子树整个进行操作
区间为（id[x], id[x] + siz[x] - 1）

P3384 【模板】重链剖分/树链剖分

题目大意

传送门
一棵 $n$ 个节点的树，节点带权。支持链加、链求和、子树加、子树求和。
$n, m \le 10^5$。

Solution

一道树链剖分的板子题
树剖之后把每个节点转移到线段树上进行区间操作即可
注意细节！！！

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

const int maxn=1e5+10;
int n,m,r,dep[maxn],fa[maxn],top[maxn],siz[maxn],id[maxn],rev[maxn],son[maxn],head[maxn],tot=0,cnt=0;
ll mod,a[maxn];
struct edge{
  int v,nxt;
}e[maxn*2];
struct seg{
  ll val,tag;
}tr[maxn*4];

namespace SGT{
  #define mid (l+r)/2
  #define lson l,mid,rt<<1
  #define rson mid+1,r,rt<<1|1
  #define lc rt<<1
  #define rc rt<<1|1
  inline void pushup(int rt){tr[rt].val=(tr[lc].val+tr[rc].val)%mod;}
  inline void pushdown(int l,int r,int rt){
  	if(tr[rt].tag>0){
  	  int t=tr[rt].tag;
  	  tr[rt].tag=0;
  	  tr[lc].val=(tr[lc].val+t*(mid-l+1))%mod;
  	  tr[rc].val=(tr[rc].val+t*(r-mid))%mod;
  	  tr[lc].tag=(tr[lc].tag+t)%mod;//+t而不是=t 
  	  tr[rc].tag=(tr[rc].tag+t)%mod;
	}
  }
  inline void build(int l=1,int r=n,int rt=1){
    if(l==r){
      tr[rt].val=rev[l]%mod;
      tr[rt].tag=0;
      return;
	}
	build(lson);
	build(rson);
	pushup(rt);
  }
  inline void update(int x,int y,ll val,int l=1,int r=n,int rt=1){
  	if(x<=l&&y>=r){
	  tr[rt].val=(tr[rt].val+val*(r-l+1))%mod;
	  tr[rt].tag=(tr[rt].tag+val)%mod;
	  return;  
	}
	pushdown(l,r,rt);
	if(x<=mid) update(x,y,val,lson);
	if(y>mid) update(x,y,val,rson);
	pushup(rt);
  }
  inline ll query(int x,int y,int l=1,int r=n,int rt=1){
  	if(x<=l&&y>=r) return tr[rt].val;
  	pushdown(l,r,rt);
  	ll res=0;
  	if(x<=mid) res=(res+query(x,y,lson))%mod;
  	if(y>mid) res=(res+query(x,y,rson))%mod;
  	return res%mod;
  }
}

inline void add(int u,int v){
  e[++tot]=(edge){v,head[u]};
  head[u]=tot;
  e[++tot]=(edge){u,head[v]};
  head[v]=tot;
}

inline void dfs1(int u,int f){
  dep[u]=dep[f]+1;
  fa[u]=f;siz[u]=1;
  son[u]=-1;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==f) continue;
  	dfs1(v,u);
  	siz[u]+=siz[v];
  	if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
  }
}

inline void dfs2(int u,int pre){
  top[u]=pre;
  id[u]=++cnt;rev[cnt]=a[u];
  if(son[u]==-1) return ;
  dfs2(son[u],pre);
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa[u]||v==son[u]) continue;
  	dfs2(v,v);
  }
}

inline void add_path(int x,int y,ll val){
  val%=mod;
  while(top[x]!=top[y]){
  	if(dep[top[x]]<dep[top[y]]) swap(x,y);
  	SGT::update(id[top[x]],id[x],val);
  	x=fa[top[x]];
  }
  if(dep[x]>dep[y]) swap(x,y);
  SGT::update(id[x],id[y],val);
}

inline ll query_path(int x,int y){
  ll res=0;
  while(top[x]!=top[y]){
  	if(dep[top[x]]<dep[top[y]]) swap(x,y);
  	res=(res+SGT::query(id[top[x]],id[x]))%mod;
  	x=fa[top[x]];
  }
  if(dep[x]>dep[y]) swap(x,y);
  res=(res+SGT::query(id[x],id[y]))%mod;
  return res;
}

int main(){
  /*2023.7.3 H_W_Y P3384 【模板】重链剖分/树链剖分 树链剖分*/ 
  scanf("%d%d%d%lld",&n,&m,&r,&mod);
  for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
  for(int i=1;i<n;i++){
  	int u,v;
  	scanf("%d%d",&u,&v);
  	add(u,v);
  }
  dfs1(r,0);dfs2(r,r);//dfs2中的pre是top[u]，所以是dfs2(r,r) 
  SGT::build();
  for(int i=1;i<=m;i++){
  	int op,u,v;ll val;
  	scanf("%d",&op);
  	if(op==1){
  	  scanf("%d%d%lld",&u,&v,&val);
	  add_path(u,v,val);
	}
	if(op==2){
	  scanf("%d%d",&u,&v);
	  printf("%lld\n",query_path(u,v)%mod);	
	}
	if(op==3){
	  scanf("%d%lld",&u,&val);
	  SGT::update(id[u],id[u]+siz[u]-1,val);
	}
	if(op==4){
	  scanf("%d",&u);
	  printf("%lld\n",SGT::query(id[u],id[u]+siz[u]-1)%mod);
	}
  }
  return 0;
}

P4211 [LNOI2014] LCA

题目大意

传送门

一棵 $n$ 个节点的有根树，定义 $dep_x$ 为 $x$ 到根的距离 $+1$。$q$ 次给出 $l, r, z$，询问
$\sum_{i=l}^{r}{dep[LCA(i,z)]}$
$n,q \le 50000$

Solution

求$\sum dep$，暴力求sum是完不成的
那我们考虑深度是什么？
是$x$到根的距离$+1$
而对于每一条边
它的距离都为$1$
这样我们就可以把距离转化到点上面
我们把$l \sim r$到根的路径上的点的权值都赋值为$1$
那么在找从$z$到根的路径上的权值之和即可

~~题解用的差分，我没看懂~~
而对于这个问题
我的想法是用一棵主席树来维护

点分治

P3806 【模板】点分治1

题目大意

传送门
给定一棵 $n$ 个点的树，询问是否存在距离为 $k$ 的点对。
$n \le 10^5$

Solution

一道点分治的模板题
通常被用在大规模处理树上路径的问题上（如同时询问树上所有路径的答案和）。

考虑把树上的路径分为两种
一种是经过根节点的，另一种是不经过根节点的
我们对于每一个节点，考虑第一种路径
又分为端点为根节点的和两个端点都不是根节点的
那么后者是由前者组成的
我们只要统计之前是否出现过$q[i]-dist[i]$的路径
就可以判断是否出现长度为$q[i]$的路径

而对于第二种路径
我们递归其子树即可

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10,inf=0x3f3f3f3f;
int n,m,head[maxn],rt,cnt=0,sum,tot=0,d[maxn],dist[maxn],q[maxn],mx[maxn],siz[maxn];
bool vis[maxn],tf[10000005],res[maxn];
struct edge{
  int v,nxt,val;
}e[maxn*2];

inline void add(int u,int v,int val){
  e[++tot]=(edge){v,head[u],val};
  head[u]=tot;
  e[++tot]=(edge){u,head[v],val};
  head[v]=tot;
}

inline int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

inline void calcsiz(int u,int fa){
  siz[u]=1;mx[u]=0;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa||vis[v]) continue;
  	calcsiz(v,u);
  	siz[u]+=siz[v];
  	mx[u]=max(mx[u],siz[v]);
  }
  mx[u]=max(mx[u],sum-siz[u]);
  if(mx[u]<mx[rt]) rt=u;
}

inline void calcdist(int u,int fa){
  d[++cnt]=dist[u];
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dist[v]=dist[u]+val;
  	calcdist(v,u);
  }
}

queue<int>tag;
inline void dfz(int u,int fa){
  tf[0]=true;//初始化 
  tag.push(0);
  vis[u]=true;
  cnt=0;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dist[v]=val;
  	calcdist(v,u);
  	for(int j=1;j<=cnt;j++)
  	  for(int k=1;k<=m;k++)
  	    if(q[k]>=d[j]) res[k]|=tf[q[k]-d[j]];//不要忽略以根为端点的情况 
  	for(int j=1;j<=cnt;j++) if(d[j]<10000000) tf[d[j]]=true,tag.push(d[j]);//注意d[j]的范围，否则会RE 
    cnt=0;
  }
  while(!tag.empty()) tf[tag.front()]=false,tag.pop();
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa||vis[v]) continue;
  	sum=siz[v];rt=0;mx[0]=inf;
  	calcsiz(v,u);calcsiz(rt,0);
  	dfz(rt,u);
  }
}

int main(){
  /*2023.7.4 H_W_Y P3806 【模板】点分治1 点分治*/
  n=read();m=read();
  for(int i=1;i<n;i++){
  	int u,v,w;
  	u=read();v=read();w=read();
  	add(u,v,w);
  }
  for(int i=1;i<=m;i++) q[i]=read();
  sum=n;rt=0;mx[rt]=inf;
  calcsiz(1,0);calcsiz(rt,0);
  dfz(rt,0);
  for(int i=1;i<=m;i++)
    if(res[i]) printf("AYE\n");
    else printf("NAY\n");
  return 0;
}

P2634 [国家集训队] 聪聪可可

题目大意

传送门
给定一棵 $n$ 个点的树，求树上距离为 $3$ 的倍数的点的对数。
$n \le 10^5$

Solution

一道点分治的模板题
对于每条路径统计即可
注意是两个不同的人选
所以计算方案数时要乘上2，$A_{2}^{2}=2$
其他的部分和上一道题没有太大区别

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10,inf=0x3f3f3f3f;
int tf[4],n,head[maxn],tot=0,cnt=0,ans=0,siz[maxn],d[3],dis[maxn],mx[maxn],rt=0,sum;
bool vis[maxn];
struct edge{
  int v,nxt,val;
}e[maxn*2];

inline int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

inline void add(int u,int v,int val){
  e[++tot]=(edge){v,head[u],val%3};
  head[u]=tot;
  e[++tot]=(edge){u,head[v],val%3};
  head[v]=tot;
}

inline void calcsiz(int u,int fa){
  siz[u]=1;mx[u]=0;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa||vis[v]) continue;
  	calcsiz(v,u);
  	siz[u]+=siz[v];
  	mx[u]=max(mx[u],siz[v]);
  }
  mx[u]=max(mx[u],sum-siz[u]);
  if(mx[u]<mx[rt]) rt=u;
}

inline void calcdist(int u,int fa){
  d[dis[u]%3]++;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dis[v]=dis[u]+val;
  	calcdist(v,u);
  }
}

inline void dfz(int u,int fa){
  tf[0]=1;
  vis[u]=true;ans++;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dis[v]=val;
  	calcdist(v,u);
  	for(int j=0;j<=2;j++)
  	  ans+=tf[(3-j)%3]*d[j]*2;//两个人去选，对于一个点对有A_2^2=2种情况，所以要*2 
  	for(int j=0;j<=2;j++) tf[j]+=d[j];
  	d[0]=d[1]=d[2]=0;
  }
  tf[0]=tf[1]=tf[2]=0;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa||vis[v]) continue;
  	rt=0;mx[rt]=inf;sum=siz[v];
  	calcsiz(v,u);calcsiz(rt,0);
  	dfz(rt,u);
  }
}

inline int gcd(int x,int y){
  if(y==0) return x;
  return gcd(y,x%y);
}

int main(){
  /*2023.7.4 H_W_Y P2634 [国家集训队] 聪聪可可 点分治*/ 
  n=read();
  for(int i=1;i<n;i++){
    int u,v,val;
	u=read();v=read();val=read();
	add(u,v,val); 
  }
  rt=0;mx[rt]=inf;sum=n;
  calcsiz(1,0);calcsiz(rt,0);
  dfz(rt,0);
  sum=n*n;
  int t=gcd(ans,sum);
  printf("%d/%d\n",ans/t,sum/t);
  return 0;
}

P4149 [IOI2011] Race

题目大意

传送门
给定一棵 $n$ 个点的树，有边权，求树上距离为 $k$ 的点对之间的边数最小值。
$n \le 10^5$

Solution

和点分治的模板题比较类似
就是在统计是否出现长度为$k$的路径同时统计其边的条数
在每一次更新的时候对答案也进行更新即可
注意细节问题：
$v=e[i].v \ne e[i].nxt$

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+10,inf=0x3f3f3f3f;
int n,k,head[maxn],tot=0,cnt=0,d[maxn],dis[maxn],siz[maxn],rt,sum,mn[1000005],ans,dd[maxn],mx[maxn];
bool res=false,tf[1000005],vis[maxn];
struct edge{
  int v,nxt,val;
}e[maxn*2];

inline int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

inline void add(int u,int v,int val){
  e[++tot]=(edge){v,head[u],val};
  head[u]=tot;
  e[++tot]=(edge){u,head[v],val};
  head[v]=tot;
}

inline void calcsiz(int u,int fa){
  mx[u]=0;siz[u]=1;
  for(int i=head[u];i;i=e[i].nxt){
    int v=e[i].v;
    if(v==fa||vis[v]) continue;
    calcsiz(v,u);
    siz[u]+=siz[v];
    mx[u]=max(mx[u],siz[v]);
  }
  mx[u]=max(mx[u],sum-siz[u]);
  if(mx[u]<mx[rt]) rt=u;
}

inline void calcdist(int u,int fa,int step){
  d[++cnt]=dis[u];dd[cnt]=step;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dis[v]=dis[u]+val;
  	calcdist(v,u,step+1);
  }
}

queue<int>tag;
inline void dfz(int u,int fa){
  vis[u]=true;
  tf[0]=true;mn[0]=0;
  tag.push(0);
  cnt=0;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v,val=e[i].val;
  	if(v==fa||vis[v]) continue;
  	dis[v]=val;
  	calcdist(v,u,1);
  	for(int j=1;j<=cnt;j++)
  	  if(k>=d[j])
  	    if(tf[k-d[j]]){
  	      res=true;
		  ans=min(ans,mn[k-d[j]]+dd[j]);	
	    }
	for(int j=1;j<=cnt;j++)
	  if(d[j]<=1000000){
	  	tf[d[j]]=true;
	  	tag.push(d[j]);
	  	mn[d[j]]=min(mn[d[j]],dd[j]); 
	  }
	cnt=0;
  }
  while(!tag.empty()) tf[tag.front()]=false,mn[tag.front()]=inf,tag.pop();
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==fa||vis[v]) continue;
  	rt=0;mx[rt]=inf;sum=siz[v];
  	calcsiz(v,u);calcsiz(rt,0);
  	dfz(rt,u);
  }
}

int main(){
  /*2023.7.4 H_W_Y P4149 [IOI2011] Race 点分治*/ 
  n=read();k=read();
  for(int i=1;i<n;i++){
  	int u,v,val;
  	u=read();v=read();val=read();
  	u++,v++;
	add(u,v,val);
  }
  rt=0;mx[rt]=inf;sum=n;
  ans=inf;
  memset(mn,0x3f,sizeof(mn));
  calcsiz(1,0);calcsiz(rt,0);
  dfz(rt,0);
  if(res) printf("%d\n",ans);
  else printf("-1\n");
  return 0;
}

20230626

bytebuffer 20230626 java nio

20230626 sso2 sso 15

20230626 pattern regex java

charbuffer 20230626 java nio

20230626 java file path

20230626 matcher regex java

20230626 files java file