模板题，详见此
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,r,p,t[100005],fa[100005],dep[100005],son[100005],id[100005],w[100005],tp[100005],name,f[400005],laz[400005],nl,nr,k,sum[100005];
vector<int>a[100005];
int dfs1(int x,int fath)
{
fa[x]=fath;
dep[x]=dep[fath]+1;
int len=a[x].size(),maxn=-1,ma=0;
sum[x]=1;
for(int i=0;i<len;i++)
{
if(a[x][i]==fath)continue;
int num=dfs1(a[x][i],x);
if(num>maxn)
{
maxn=num;
ma=a[x][i];
}
sum[x]+=num;
}
son[x]=ma;
return sum[x];
}
void dfs2(int x,int topp)
{
id[x]=++name;
w[name]=t[x];
tp[x]=topp;
if(!son[x])return;
dfs2(son[x],topp);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==son[x]||a[x][i]==fa[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
void build(int x,int l,int r)
{
if(l==r)
{
f[x]=w[l]%p;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
f[x]=f[ls(x)]+f[rs(x)];
}
void fix(int x,int l,int r,int kt)
{
f[x]+=(r-l+1)*kt,f[x]%=p;
laz[x]+=kt,laz[x]%=p;
}
void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
fix(ls(x),l,mid,laz[x]);
fix(rs(x),mid+1,r,laz[x]);
laz[x]=0;
}
int search(int x,int l,int r)
{
if(l>=nl&&nr>=r)return f[x];
int mid=(l+r)>>1,num=0;
pushdown(x,l,r);
if(mid>=nl)num+=search(ls(x),l,mid),num%=p;
if(nr>mid)num+=search(rs(x),mid+1,r),num%=p;
return num;
}
void update(int x,int l,int r)
{
if(l>=nl&&nr>=r)
{
f[x]+=(r-l+1)*k,f[x]%=p;
laz[x]+=k,laz[x]%=p;
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(nr>mid)update(rs(x),mid+1,r);
f[x]=f[ls(x)]+f[rs(x)],f[x]%=p;
}
void update_jump(int x,int y)
{
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]])swap(x,y);
nr=id[x],nl=id[tp[x]];
update(1,1,n);
x=fa[tp[x]];
}
if(id[x]>id[y])swap(x,y);
nl=id[x],nr=id[y];
update(1,1,n);
}
int search_jump(int x,int y)
{
int num=0;
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]])swap(x,y);
nl=id[tp[x]],nr=id[x];
num+=search(1,1,n),num%=p;
x=fa[tp[x]];
}
if(id[x]>id[y])swap(x,y);
nl=id[x],nr=id[y];
return (num+search(1,1,n))%p;
}
void update_tree(int x)
{
nl=id[x],nr=id[x]+sum[x]-1;
update(1,1,n);
}
int search_tree(int x)
{
nl=id[x],nr=id[x]+sum[x]-1;
return search(1,1,n);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int T;
scanf("%d",&T);
if(T==1)
{
int x,y;
scanf("%d%d%d",&x,&y,&k);
k%=p;
update_jump(x,y);
}
if(T==2)
{
int x,y;
scanf("%d%d",&x,&y);
int ans=search_jump(x,y);
printf("%d\n",ans);
}
if(T==3)
{
int x;
scanf("%d%d",&x,&k);
k%=p;
update_tree(x);
}
if(T==4)
{
int x;
scanf("%d",&x);
int ans=search_tree(x);
printf("%d\n",ans);
}
}
return 0;
}
2、P3313 [SDOI2014]旅行（较简单的变式题）
因为有宗教的存在，传统的线段树＋树链剖分已无法解决此题，必须要想办法处理这个问题。
实际上也挺好想，就建立 \(10^5\) 个线段树，每棵线段树对应一个宗教。
操作1：将之前宗教所处的线段树对应的点赋为 \(0\)，再添加到新宗教的线段树即可。
操作2：改值即可。
操作3：树剖求此线段树的和。
操作4：树剖求此线段树的最大值。
动态开点即可。
#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
const int N=1e5+5;
int n,q,w[N],c[N],fa[N],dep[N],topp[N],id[N],cnt,siz[N],son[N],rt[N],nl,nr,k;
vector<int>a[N];
struct node
{
int num,maxn,ls,rs;
}f[20*N];
int dfs1(int x,int fath)
{
dep[x]=dep[fath]+1;
fa[x]=fath;
siz[x]=1;
int len=a[x].size(),maxn=0;
for(int i=0;i<len;i++)
{
if(a[x][i]==fath)continue;
int num=dfs1(a[x][i],x);
if(num>maxn)maxn=num,son[x]=a[x][i];
siz[x]+=num;
}
return siz[x];
}
void dfs2(int x,int tp)
{
topp[x]=tp;
id[x]=++cnt;
if(son[x])dfs2(son[x],tp);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==fa[x]||a[x][i]==son[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
void pushup(int x)
{
f[x].num=f[f[x].ls].num+f[f[x].rs].num;
f[x].maxn=max(f[f[x].ls].maxn,f[f[x].rs].maxn);
}
void update(int &x,int l,int r)
{
if(!x)x=++cnt;
if(l==r)
{
f[x].num=f[x].maxn=k;
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(f[x].ls,l,mid);
else update(f[x].rs,mid+1,r);
pushup(x);
}
int search1(int x,int l,int r)
{
if(!x)return 0;
if(l>=nl&&r<=nr)return f[x].num;
int mid=(l+r)>>1;
int sum=0;
if(mid>=nl)sum+=search1(f[x].ls,l,mid);
if(mid<nr)sum+=search1(f[x].rs,mid+1,r);
return sum;
}
int search2(int x,int l,int r)
{
if(!x)return 0;
if(l>=nl&&r<=nr)return f[x].maxn;
int mid=(l+r)>>1;
int maxn=0;
if(mid>=nl)maxn=max(maxn,search2(f[x].ls,l,mid));
if(mid<nr)maxn=max(maxn,search2(f[x].rs,mid+1,r));
return maxn;
}
int search_road_sum(int x,int y)
{
int t=c[x],sum=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
sum+=search1(rt[t],1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
sum+=search1(rt[t],1,n);
return sum;
}
int search_road_max(int x,int y)
{
int t=c[x],maxn=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
maxn=max(maxn,search2(rt[t],1,n));
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
maxn=max(maxn,search2(rt[t],1,n));
return maxn;
}
signed main()
{
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&c[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)
{
nl=id[i],k=w[i];
update(rt[c[i]],1,n);
}
for(int i=1;i<=q;i++)
{
char ch[3];
scanf("%s",ch+1);
int x,y;
scanf("%lld%lld",&x,&y);
if(ch[1]=='C'&&ch[2]=='C')
{
nl=id[x],k=0;
update(rt[c[x]],1,n);
c[x]=y,k=w[x];
update(rt[c[x]],1,n);
}
if(ch[1]=='C'&&ch[2]=='W')
{
nl=id[x],k=y;
update(rt[c[x]],1,n);
w[x]=y;
}
if(ch[1]=='Q'&&ch[2]=='S')
{
int ans=search_road_sum(x,y);
printf("%lld\n",ans);
}
if(ch[1]=='Q'&&ch[2]=='M')
{
int ans=search_road_max(x,y);
printf("%lld\n",ans);
}
}
return 0;
}
3、P2590 [ZJOI2008]树的统计（练习题）
模板练习，不懂见开始的那个博客。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=3e4+5;
int n,dep[N],son[N],fa[N],topp[N],id[N],t[N],w[N],f[4*N],m[4*N],cnt,nl,nr,k;
vector<int>a[N];
int dfs1(int x,int fath)
{
fa[x]=fath;
dep[x]=dep[fath]+1;
int maxn=0,sum=1;
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==fath)continue;
int num=dfs1(a[x][i],x);
if(num>maxn)maxn=num,son[x]=a[x][i];
sum+=num;
}
return sum;
}
void dfs2(int x,int tp)
{
id[x]=++cnt;
w[cnt]=t[x];
topp[x]=tp;
int len=a[x].size();
if(son[x])dfs2(son[x],tp);
for(int i=0;i<len;i++)
{
if(a[x][i]==fa[x]||a[x][i]==son[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=f[ls(x)]+f[rs(x)];
m[x]=max(m[ls(x)],m[rs(x)]);
}
void build(int x,int l,int r)
{
if(l==r)
{
f[x]=m[x]=w[l];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void update(int x,int l,int r)
{
if(l==r)
{
f[x]=m[x]=k;
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
else update(rs(x),mid+1,r);
pushup(x);
}
int search1(int x,int l,int r)
{
if(l>=nl&&r<=nr)return f[x];
int mid=(l+r)>>1,sum=0;
if(mid>=nl)sum+=search1(ls(x),l,mid);
if(mid<nr)sum+=search1(rs(x),mid+1,r);
return sum;
}
int search2(int x,int l,int r)
{
if(l>=nl&&r<=nr)return m[x];
int mid=(l+r)>>1,maxn=-30005;
if(mid>=nl)maxn=max(maxn,search2(ls(x),l,mid));
if(mid<nr)maxn=max(maxn,search2(rs(x),mid+1,r));
return maxn;
}
int search1_road(int x,int y)
{
int sum=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
sum+=search1(1,1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
sum+=search1(1,1,n);
return sum;
}
int search2_road(int x,int y)
{
int maxn=-30005;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
maxn=max(maxn,search2(1,1,n));
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
maxn=max(maxn,search2(1,1,n));
return maxn;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
char opt[10];
scanf("%s",opt);
if(opt[0]=='C')
{
int x;
scanf("%d%d",&x,&k);
nl=id[x];
update(1,1,n);
}
else if(opt[1]=='M')
{
int x,y;
scanf("%d%d",&x,&y);
int ans=search2_road(x,y);
printf("%d\n",ans);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
int ans=search1_road(x,y);
printf("%d\n",ans);
}
}
return 0;
}
4、P1505 [国家集训队]旅游（练习题）
为什么一道板题要搞得这么花里胡哨啊。
边权转换为点权，对于每一条边的权值，转换到儿子上面即可，根节点不进行遍历。
取相反数也很简单，区间和取反，区间最小值为区间最大值的相反数，区间最大值为区间最小值的相反数。
注意细节，这题细节特别多，如求路径时两点的 LCA 是不能计算的，因为 LCA 与父亲的路径并没有更新，还有特判根节点是不能取的，具体看代码。（有亿点长，应该是这个系列第二长的了）
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+5;
int n,m,t[N],dep[N],fa[N],siz[N],son[N],cnt,w[N],id[N],topp[N],f[4*N],laz[4*N],ma[4*N],mi[4*N],nl,nr,k,p[N];
struct node
{
int name,to,data;
};
vector<node>a[N];
int dfs1(int x,int fath)
{
dep[x]=dep[fath]+1;
fa[x]=fath;
siz[x]=1;
int len=a[x].size(),maxn=0;
for(int i=0;i<len;i++)
{
if(a[x][i].to==fath)continue;
p[a[x][i].name]=a[x][i].to;
t[a[x][i].to]=a[x][i].data;
int num=dfs1(a[x][i].to,x);
if(num>maxn)maxn=num,son[x]=a[x][i].to;
siz[x]+=num;
}
return siz[x];
}
void dfs2(int x,int tp)
{
topp[x]=tp;
id[x]=++cnt;
w[cnt]=t[x];
if(son[x])dfs2(son[x],tp);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i].to==fa[x]||a[x][i].to==son[x])continue;
dfs2(a[x][i].to,a[x][i].to);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=f[ls(x)]+f[rs(x)];
ma[x]=max(ma[ls(x)],ma[rs(x)]);
mi[x]=min(mi[ls(x)],mi[rs(x)]);
}
void build(int x,int l,int r)
{
if(l==r)
{
f[x]=mi[x]=ma[x]=w[l];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
inline void fix(int x,int l,int r,int kt)
{
f[x]=-f[x];
int kp=mi[x];
mi[x]=-ma[x];
ma[x]=-kp;
laz[x]^=1;
}
inline void pushdown(int x,int l,int r)
{
if(!laz[x])return;
int mid=(l+r)>>1;
fix(ls(x),l,mid,laz[x]);
fix(rs(x),mid+1,r,laz[x]);
laz[x]=0;
}
void update(int x,int l,int r)
{
if(l>=nl&&r<=nr)
{
f[x]=-f[x];
int kp=mi[x];
mi[x]=-ma[x];
ma[x]=-kp;
laz[x]^=1;
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(mid<nr)update(rs(x),mid+1,r);
pushup(x);
}
void update2(int x,int l,int r)
{
if(l==r)
{
f[x]=mi[x]=ma[x]=k;
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update2(ls(x),l,mid);
else update2(rs(x),mid+1,r);
pushup(x);
}
int search(int x,int l,int r)
{
if(l>=nl&&r<=nr)return f[x];
pushdown(x,l,r);
int mid=(l+r)>>1,sum=0;
if(mid>=nl)sum+=search(ls(x),l,mid);
if(mid<nr)sum+=search(rs(x),mid+1,r);
return sum;
}
int search2(int x,int l,int r)
{
if(l>=nl&&r<=nr)return ma[x];
pushdown(x,l,r);
int mid=(l+r)>>1,maxn=-1e9;
if(mid>=nl)maxn=max(maxn,search2(ls(x),l,mid));
if(mid<nr)maxn=max(maxn,search2(rs(x),mid+1,r));
return maxn;
}
int search3(int x,int l,int r)
{
if(l>=nl&&r<=nr)return mi[x];
pushdown(x,l,r);
int mid=(l+r)>>1,minn=1e9;
if(mid>=nl)minn=min(minn,search3(ls(x),l,mid));
if(mid<nr)minn=min(minn,search3(rs(x),mid+1,r));
return minn;
}
void update_point(int x)
{
nl=id[p[x]];
update2(1,2,n);
}
void update_road(int x,int y)
{
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
update(1,2,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x]+1,nr=id[y];
if(nl<=nr)update(1,2,n);
}
int search_road(int x,int y)
{
int sum=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
sum+=search(1,2,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x]+1,nr=id[y];
if(nl<=nr)sum+=search(1,2,n);
return sum;
}
int search2_road(int x,int y)
{
int maxn=-1e9;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
maxn=max(maxn,search2(1,2,n));
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x]+1,nr=id[y];
if(nl<=nr)maxn=max(maxn,search2(1,2,n));
return maxn;
}
int search3_road(int x,int y)
{
int minn=1e9;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
minn=min(minn,search3(1,2,n));
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x]+1,nr=id[y];
if(nl<=nr)minn=min(minn,search3(1,2,n));
return minn;
}
signed main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u++,v++;
a[u].push_back((node){i,v,w});
a[v].push_back((node){i,u,w});
}
dfs1(1,0);
dfs2(1,1);
build(1,2,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
char opt[5];
scanf("%s",opt+1);
if(opt[1]=='S')
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
int ans=search_road(x,y);
printf("%d\n",ans);
}
if(opt[1]=='N')
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
update_road(x,y);
}
if(opt[1]=='C')
{
int x;
scanf("%d%d",&x,&k);
update_point(x);
}
if(opt[1]=='M'&&opt[2]=='I')
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
int ans=search3_road(x,y);
printf("%d\n",ans);
}
if(opt[1]=='M'&&opt[2]=='A')
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
int ans=search2_road(x,y);
printf("%d\n",ans);
}
}
return 0;
}
5、P2486 [SDOI2011]染色（较简单的变式题）
求树上颜色段的和，很明显树剖的部分不需要发生任何改变，仅仅改变线段树维护即可。
线段树多维护两个值，\(f_i\) 代表区间和个数，\(lc_i,rc_i\) 代表区间 \(i\) 最左边与最右边的颜色。
合并时判断合并两边颜色是否相同，若相同，则颜色段数量减一。
操作1：区间修改，打上懒标记即可。
操作2：在跳时直接可以提前判断链的顶端是否与顶端的父亲颜色相等，然后改变方案数，合并时就不用再减去方案数了。
本题要求对线段树掌握熟练。
#include<iostream>
#include<cstdio>
#include<vector>
#define N 100005
using namespace std;
int n,m,t[N],son[N],fa[N],dep[N],to[N],id[N],w[N],cnt,f[4*N],laz[4*N],lc[4*N],rc[4*N],nl,nr,k;
vector<int>a[N];
int dfs1(int x,int fath)
{
fa[x]=fath;
dep[x]=dep[fa[x]]+1;
int maxn=-1,len=a[x].size(),num=1;
for(int i=0;i<len;i++)
{
if(a[x][i]==fa[x])continue;
int ans=dfs1(a[x][i],x);
num+=ans;
if(ans>maxn)son[x]=a[x][i],maxn=ans;
}
return num;
}
void dfs2(int x,int topp)
{
to[x]=topp;
id[x]=++cnt;
w[cnt]=t[x];
if(!son[x])return;
dfs2(son[x],to[x]);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==fa[x]||a[x][i]==son[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=f[ls(x)]+f[rs(x)];
lc[x]=lc[ls(x)];
rc[x]=rc[rs(x)];
if(rc[ls(x)]==lc[rs(x)])f[x]--;
}
void build(int x,int l,int r)
{
if(l==r)
{
f[x]=1;
lc[x]=w[l];
rc[x]=w[l];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void fix(int x,int kt)
{
f[x]=1;
lc[x]=rc[x]=kt;
laz[x]=kt;
}
inline void pushdown(int x)
{
if(laz[x]==0)return;
fix(ls(x),laz[x]);
fix(rs(x),laz[x]);
laz[x]=0;
}
void update(int x,int l,int r)
{
if(nl<=l&&r<=nr)
{
f[x]=1;
lc[x]=rc[x]=laz[x]=k;
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(mid<nr)update(rs(x),mid+1,r);
pushup(x);
}
int search(int x,int l,int r)
{
if(l>=nl&&r<=nr)return f[x];
pushdown(x);
int mid=(l+r)>>1,num=0;
if(mid>=nl)num+=search(ls(x),l,mid);
if(mid<nr)num+=search(rs(x),mid+1,r);
if(mid>=nl&&mid<nr&&rc[ls(x)]==lc[rs(x)])num--;
return num;
}
int getting(int x,int l,int r)
{
if(l==r)return lc[x];
pushdown(x);
int mid=(l+r)>>1;
if(mid>=nl)return getting(ls(x),l,mid);
return getting(rs(x),mid+1,r);
}
void update_jump(int x,int y)
{
while(to[x]!=to[y])
{
if(dep[to[x]]<dep[to[y]])swap(x,y);
nr=id[x],nl=id[to[x]];
update(1,1,n);
x=fa[to[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
update(1,1,n);
}
int search_jump(int x,int y)
{
int num=0;
while(to[x]!=to[y])
{
if(dep[to[x]]<dep[to[y]])swap(x,y);
nl=id[to[x]],nr=id[x];
num+=search(1,1,n);
x=to[x];
nl=id[x];
int fi=getting(1,1,n);
x=fa[x];
nl=id[x];
int se=getting(1,1,n);
if(fi==se)num--;
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
num+=search(1,1,n);
return num;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
for(int i=1;i<n;i++)
{
int fi,se;
scanf("%d%d",&fi,&se);
a[fi].push_back(se);
a[se].push_back(fi);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=m;i++)
{
char T;
cin>>T;
int x,y;
scanf("%d%d",&x,&y);
if(T=='C')
{
scanf("%d",&k);
update_jump(x,y);
}
else
{
int ans=search_jump(x,y);
printf("%d\n",ans);
}
}
return 0;
}
6、P3258 松鼠的新家（练习题）
每次对 \(fa_i\) 到 \(i+1\) 加 \(1\) 即可（\(fa_i\) 为 \(i\) 的父节点）。
选择偷懒
求 \(i\) 到 \(i+1\) 的 LCA。
然后进行树上差分。
假设 \(i\) 与 \(i+1\) 的 LCA 为 \(k\)，\(fk\) 为 \(k\) 的父节点。
那么将 \(f_i=f_i+1,f_{i+1}=f_{i+1}+1,f_k=f_k-1,f_{fk}=f_{fk}-1\)
递归向下，回溯求解。
由于 \(i\) 节点返回不需要加值，所以把原式中 \(i\) 改为 \(fa_i\) 即可。
由于得涉及树剖，倍增求 LCA 改成树剖即可。
这里没有用树剖，懒得打。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,t[300005],dep[300005],f[300005][25],dp[300005];
vector<int>a[300005];
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
int len=a[x].size();
for(int i=0;i<len;i++)if(a[x][i]!=fa)dfs(a[x][i],x);
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int Get(int x)
{
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==f[x][0])continue;
Get(a[x][i]);
dp[x]+=dp[a[x][i]];
}
return dp[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
dfs(1,0);
for(int i=2;i<=n;i++)
{
int k=lca(t[i],t[i-1]);
dp[t[i]]++,dp[t[i-1]]++,dp[k]--,dp[f[k][0]]--;
dp[t[i]]--,dp[f[t[i]][0]]++;
}
Get(1);
for(int i=1;i<=n;i++)printf("%d\n",dp[i]);
return 0;
}
7、P4069 [SDOI2016]游戏（合李超线段树）（暂不会李超线段树）
8、P4211 [LNOI2014]LCA（树剖求区间 LCA，较难想到）
可以想到，求 \(dep[LCA(x,y)]\) 实际上是 \(LCA(x,y)\) 到根的路径加一。
貌似感觉什么都没说。
但是如果换一种方式看，就有新的发现，把 \(dep[LCA(x,y)]\) 看成 \(x\) 走到根与 \(y\) 走到根的公共路径和加一。
那这样就会很不一样，我们只要标记出 \(x\) 所走的路径，再走 \(y\) 统计和即可，由于最后要加一，所以可以把 \(x\) 走过的边改为标记走过的点，这样就可以对 \(1\) 到 \(x\) 的路径 \(+1\)，再查询 \(1\) 到 \(y\) 的路径和就行了。
每次询问树剖暴力更新 \(l\) 至 \(r\) 到 \(1\) 的值，最后求 \(z\) 到 \(1\) 的路径和。
这个很明显会 T。
考虑优化。
上述复杂度为 \(O(n\times\log_2^2(n)\times q)\)
\(n\times\log_2^2(n)\) 为树剖复杂度，很难避免，选择优化掉 \(q\)。
在每一次做区间题时，想想差分，本题利用差分求区间查询，对于每一次查询，分开为 \((l-1,z)\) 与 \((r,z)\)，然后按第一位为关键字排序，每次先进行从上一次的点更新到这次的点，再计算答案即可。
复杂度：\(O(n\times\log_2^2(n))\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+5;
const int mod=201314;
int n,m,dep[N],fa[N],siz[N],son[N],cnt,id[N],topp[N],f[4*N],laz[4*N],nl,nr,k,cnp,ans[N][2];
vector<int>a[N];
struct node
{
int name,data,num;
bool flag;
}t[2*N];
int cmp(node fi,node se)
{
return fi.data<se.data;
}
int dfs1(int x,int fath)
{
dep[x]=dep[fath]+1;
fa[x]=fath;
siz[x]=1;
int len=a[x].size(),maxn=0;
for(int i=0;i<len;i++)
{
int num=dfs1(a[x][i],x);
if(num>maxn)maxn=num,son[x]=a[x][i];
siz[x]+=num;
}
return siz[x];
}
void dfs2(int x,int tp)
{
topp[x]=tp;
id[x]=++cnt;
if(son[x])dfs2(son[x],tp);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==son[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=f[ls(x)]+f[rs(x)];
f[x]%=mod;
}
inline void fix(int x,int l,int r,int kt)
{
f[x]+=(r-l+1)*kt;
f[x]%=mod;
laz[x]+=kt;
laz[x]%=mod;
}
inline void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
fix(ls(x),l,mid,laz[x]);
fix(rs(x),mid+1,r,laz[x]);
laz[x]=0;
}
void update(int x,int l,int r)
{
if(l>=nl&&r<=nr)
{
f[x]+=(r-l+1)*k;
f[x]%=mod;
laz[x]+=k;
laz[x]%=mod;
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(mid<nr)update(rs(x),mid+1,r);
pushup(x);
}
int search(int x,int l,int r)
{
if(l>=nl&&r<=nr)return f[x];
pushdown(x,l,r);
int mid=(l+r)>>1,sum=0;
if(mid>=nl)sum+=search(ls(x),l,mid);
if(mid<nr)sum+=search(rs(x),mid+1,r);
return sum;
}
void update_road(int x,int y)
{
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
update(1,1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
update(1,1,n);
}
int search_road(int x,int y)
{
int sum=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
sum+=search(1,1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
sum+=search(1,1,n);
return sum;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=2;i<=n;i++)
{
int u;
scanf("%lld",&u);
a[u+1].push_back(i);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
x++,y++,z++;
t[++cnp].name=i;
t[cnp].data=x-1;
t[cnp].num=z;
t[cnp].flag=0;
t[++cnp].name=i;
t[cnp].data=y;
t[cnp].num=z;
t[cnp].flag=1;
}
sort(t+1,t+1+cnp,cmp);
int bef=1;
k=1;
for(int i=1;i<=cnp;i++)
{
for(int j=bef;j<=t[i].data;j++)update_road(1,j);
bef=t[i].data+1;
ans[t[i].name][t[i].flag]=search_road(1,t[i].num)%mod;
}
for(int i=1;i<=m;i++)printf("%lld\n",(ans[i][1]-ans[i][0]%mod+mod)%mod);
return 0;
}
9、P4592 [TJOI2018]异或（树剖+可持久化01trie）（未做）
10、P5305 [GXOI/GZOI2019]旧词（会了 P4211 不算特别难）
与第八题一模一样。
由于有指数，所以先预处理所有深度的贡献，即 \(dep^k-(dep-1)^k\)，然后预处理出来线段树上所有点的深度贡献值，再求前缀和，然后更新线段树时求前缀和即可。
好水的黑题
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e4+5;
const int mod=998244353;
int n,m,dep[N],fa[N],siz[N],son[N],cnt,id[N],topp[N],f[4*N],laz[4*N],nl,nr,k,cnp,ans[N],dc[N],res[N];
vector<int>a[N];
int quick_pow(int x,int y)
{
if(y==0)return 0;
int sum=1,num=x;
while(y)
{
if(y&1)sum*=num,sum%=mod;
num*=num;
num%=mod;
y>>=1;
}
return sum;
}
struct node
{
int name,data,num;
}t[2*N];
int cmp(node fi,node se)
{
return fi.data<se.data;
}
int dfs1(int x,int fath)
{
dep[x]=dep[fath]+1;
fa[x]=fath;
siz[x]=1;
int len=a[x].size(),maxn=0;
for(int i=0;i<len;i++)
{
int num=dfs1(a[x][i],x);
if(num>maxn)maxn=num,son[x]=a[x][i];
siz[x]+=num;
}
return siz[x];
}
void dfs2(int x,int tp)
{
topp[x]=tp;
id[x]=++cnt;
if(son[x])dfs2(son[x],tp);
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i]==son[x])continue;
dfs2(a[x][i],a[x][i]);
}
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x)
{
f[x]=f[ls(x)]+f[rs(x)];
f[x]%=mod;
}
inline void fix(int x,int l,int r,int kt)
{
f[x]+=(res[r]-res[l-1])*kt;
f[x]%=mod;
laz[x]+=kt;
laz[x]%=mod;
}
inline void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
fix(ls(x),l,mid,laz[x]);
fix(rs(x),mid+1,r,laz[x]);
laz[x]=0;
}
void update(int x,int l,int r)
{
if(l>=nl&&r<=nr)
{
f[x]+=res[r]-res[l-1];
f[x]%=mod;
laz[x]++;
laz[x]%=mod;
return;
}
pushdown(x,l,r);
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(mid<nr)update(rs(x),mid+1,r);
pushup(x);
}
int search(int x,int l,int r)
{
if(l>=nl&&r<=nr)return f[x];
pushdown(x,l,r);
int mid=(l+r)>>1,sum=0;
if(mid>=nl)sum+=search(ls(x),l,mid);
if(mid<nr)sum+=search(rs(x),mid+1,r);
return sum;
}
void update_road(int x,int y)
{
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
update(1,1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
update(1,1,n);
}
int search_road(int x,int y)
{
int sum=0;
while(topp[x]!=topp[y])
{
if(dep[topp[x]]<dep[topp[y]])swap(x,y);
nl=id[topp[x]],nr=id[x];
sum+=search(1,1,n);
x=fa[topp[x]];
}
if(dep[x]>dep[y])swap(x,y);
nl=id[x],nr=id[y];
sum+=search(1,1,n);
return sum;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)dc[i]=((quick_pow(i,k)-quick_pow(i-1,k))%mod+mod)%mod;
for(int i=2;i<=n;i++)
{
int u;
scanf("%lld",&u);
a[u].push_back(i);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)res[id[i]]=dc[dep[i]];
for(int i=1;i<=n;i++)res[i]=(res[i]+res[i-1])%mod;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld",&x,&y);
t[++cnp].name=i;
t[cnp].data=x;
t[cnp].num=y;
}
sort(t+1,t+1+cnp,cmp);
int bef=1;
for(int i=1;i<=cnp;i++)
{
for(int j=bef;j<=t[i].data;j++)update_road(1,j);
bef=t[i].data+1;
ans[t[i].name]=search_road(1,t[i].num)%mod;
}
for(int i=1;i<=m;i++)printf("%lld\n",(ans[i]%mod+mod)%mod);
return 0;
}