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;
}