登录
← 返回首页 | 代码片段 › 4 树上问题 › 4.3 树论综合 › 树论综合 / 搜索
JSON MD

4.3 树论综合

斯坦纳树 (游览计划) 方格图
80 行
CPP JSON
【斯坦纳树 (游览计划)(方格图)】 斯坦纳树(Steiner Tree)模板,连接指定点集的最小树。 核心函数: void in(Re &x) — 核心算法函数 void SPFA(Re s) — SPFA最短路 void dfs(Re i,Re j,Re s) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:Steiner_Tree, PRE, QAQ 关键配置: N=12 说明:freopen("123.txt","r",stdin);
C++ 79 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12;
int n,m,ct,A[N][N],B[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Steiner_Tree{
	struct PRE{int i,j,s;PRE(Re I=0,Re J=0,Re S=0){i=I,j=J,s=S;}}pre[N][N][1024+3];
	int vis[N][N],dp[N][N][1024+3],wx[4]={-1,0,1,0},wy[4]={0,1,0,-1};
	struct QAQ{int x,y;QAQ(Re X=0,Re Y=0){x=X,y=Y;}};
	queue<QAQ>Q;
	inline void SPFA(Re s){
		while(!Q.empty()){
			QAQ now=Q.front();Q.pop();
			Re x=now.x,y=now.y;vis[x][y]=0;
			for(Re o=0;o<4;++o){
				Re nx=x+wx[o],ny=y+wy[o];
				if(nx<1||nx>n||ny<1||ny>m)continue;
				if(dp[nx][ny][s]>dp[x][y][s]+B[nx][ny]){
					dp[nx][ny][s]=dp[x][y][s]+B[nx][ny],pre[nx][ny][s]=PRE(x,y,s);
					if(!vis[nx][ny])Q.push(QAQ(nx,ny)),vis[nx][ny]=1;
				}
			}
		}
	}
	int Ans[N][N];
	inline void dfs(Re i,Re j,Re s){
		Ans[i][j]=1;PRE to=pre[i][j][s];
		if(to.s){
			dfs(to.i,to.j,to.s);
			if(to.i==i&&to.j==j)dfs(to.i,to.j,s^to.s);
		}
	}
	inline void sakura(){
		memset(dp,63,sizeof(dp));
		Re V=(1<<ct)-1,inf=dp[0][0][0];
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				if(A[i][j])dp[i][j][1<<A[i][j]-1]=0;
		for(Re s=0;s<=V;++s){
			for(Re i=1;i<=n;++i)
				for(Re j=1;j<=m;++j){
					for(Re t=(s-1)&s,tmp;t;t=(t-1)&s)
						if((tmp=dp[i][j][t]+dp[i][j][s^t]-B[i][j])<dp[i][j][s])
							dp[i][j][s]=tmp,pre[i][j][s]=PRE(i,j,t);
					if(dp[i][j][s]!=inf)Q.push(QAQ(i,j)),vis[i][j]=1;
				}
			SPFA(s);
		}
		Re ans=2e9,x,y;
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				if(A[i][j])ans=dp[x=i][y=j][V];
		printf("%d\n",ans);
		dfs(x,y,V);
		for(Re i=1;i<=n;puts(""),++i)
			for(Re j=1;j<=m;++j)
				putchar(A[i][j]?'x':(Ans[i][j]?'o':'_'));
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j){
			in(B[i][j]);
			if(!B[i][j])A[i][j]=++ct;
		}
	T1.sakura();
}
斯坦纳树 普通无向图
45 行
CPP JSON
【斯坦纳树(普通无向图)】 斯坦纳树(Steiner Tree)模板,连接指定点集的最小树。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void SPFA(Re s) — SPFA最短路 核心结构体:QAQ 关键配置: N=103,M=503 说明:freopen("123.txt","r",stdin);
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=503;
int n,m,o,x,y,z,K,ans,pan[N],head[N],dp[N][1024+3];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void SPFA(Re s){
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dp[x][s]+a[i].w<dp[to=a[i].to][s]){
				dp[to][s]=dp[x][s]+a[i].w;
				if(!pan[to])Q.push(to),pan[to]=1;
			}
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(K);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	memset(dp,63,sizeof(dp));Re inf=dp[0][0];
	for(Re i=1;i<=K;++i)in(x),dp[x][1<<i-1]=0,ans=x;
	Re V=(1<<K)-1;
	for(Re s=0;s<=V;++s){
		for(Re i=1;i<=n;++i){
			for(Re t=(s-1)&s;t;t=(t-1)&s)
				dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s^t]);
			if(dp[i][s]!=inf)Q.push(i),pan[i]=1;
		}
		SPFA(s);
	}
	printf("%d ",dp[ans][V]);
}
DFS序+分治 Lomsat gelral
50 行
CPP JSON
【DFS序+分治(Lomsat gelral)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 void sakura(Re L,Re R) — 后缀数组 核心结构体:QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 49 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,tmp,dfn_O,A[N],Q[N],cnt[N],dfn[N],idx[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
    idx[dfn[x]=++dfn_O]=x,size[x]=1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
    while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
    ++cnt[Q[++t]=A[x]];
    if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
    else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void sakura(Re L,Re R){
    if(L==R){if(size[idx[L]]==1)Ans[idx[L]]=A[idx[L]];return;}
    Re mid=L+R>>1;
    sakura(L,mid),sakura(mid+1,R);
    Re p=mid;CL();
    for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
        insert(idx[i]);
        if(j<=mid)continue;
        while(p<j)insert(idx[++p]);
        Ans[idx[i]]=ans;
    }
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    dfs(1,0),sakura(1,n);
    for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
Dsu on tree Lomsat gelral
54 行
CPP JSON
【Dsu on tree(Lomsat gelral)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 void addson(Re x,Re fa) — 加法更新 void sakura(Re x,Re fa) — 后缀数组 核心结构体:QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,K,tmp,A[N],Q[N],cnt[N],son[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
	size[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x),size[x]+=size[to];
			if(size[to]>size[son[x]])son[x]=to;
		}
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=A[x]];
	if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
	else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
	if(son[x])sakura(son[x],x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
	insert(x),Ans[x]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0),sakura(1,0);
	for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
Prufer序列 get_prufer
39 行
CPP JSON
【Prufer序列】 Prufer 序列模板,n 个节点的有标号无根树计数。 核心函数: void in(Re &x) — 核心算法函数 LL get_prufer(无参数) — 获取值 LL get_fa(无参数) — 获取值 关键配置: N=5e6+3 说明:printf("Prufer: ");for(Re i=1;i<=n-2;++i)printf("%d ",pf[i]);puts("");;printf("fa: ");for(Re i=1;i<=n-1;++i)printf("%d ",fa[i]);puts("");;freopen("123.txt","r",stdin);
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e6+3;
int n,op,fa[N],pf[N],son[N];LL ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL get_prufer(){
	for(Re i=1;i<=n-1;++i)in(fa[i]),++son[fa[i]];
	for(Re i=1,j=1;i<=n-2;++i,++j){
		while(son[j])++j;pf[i]=fa[j];
		while(i<=n-2&&!--son[pf[i]]&&pf[i]<j)pf[i+1]=fa[pf[i]],++i;
	}
//	printf("Prufer: ");for(Re i=1;i<=n-2;++i)printf("%d ",pf[i]);puts("");
	for(Re i=1;i<=n-2;++i)ans^=(LL)i*pf[i];
	return ans;
}
inline LL get_fa(){
	for(Re i=1;i<=n-2;++i)in(pf[i]),++son[pf[i]];pf[n-1]=n;
	for(Re i=1,j=1;i<=n-1;++i,++j){
		while(son[j])++j;fa[j]=pf[i];
		while(i<=n-1&&!--son[pf[i]]&&pf[i]<j)fa[pf[i]]=pf[i+1],++i;
	}
//	printf("fa: ");for(Re i=1;i<=n-1;++i)printf("%d ",fa[i]);puts("");
	for(Re i=1;i<=n-1;++i)ans^=(LL)i*fa[i];
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(op),printf("%lld\n",op<2?get_prufer():get_fa());
}
基环树 Island 求基环树森林直径之和
60 行
CPP JSON
【基环树(Island 求基环树森林直径之和)】 基环树(Pseudo Tree)模板,含一个环的 n 节点 n 边连通图。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 LL max(LL a,LL b) — 核心算法函数 int find_circle(Re x,Re p) — 查找(并查集寻根/二分查找) void Tree_dp(Re x) — 核心算法函数 LL pp(Re j) — 核心算法函数 LL sakura(Re root) — 后缀数组 核心结构体:QAQ 关键配置: N=1e6+3
C++ 60 行 CPP
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#define Re register int
const int N=1e6+3;
#define LL long long
int n,m,x,y,o=1,h,t,st,cnt,In[N],cir[N],pan[N],head[N];LL ans,tmp,Q[N<<1],S[N<<1],dp[N<<1],dis[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline LL max(LL a,LL b){return a>b?a:b;}
inline int find_circle(Re x,Re p){
	if(In[x]){st=x,cir[++cnt]=x,pan[x]=1;return 1;}
	In[x]=1;
	for(Re i=head[x];i;i=a[i].next)
		if(i!=(p^1)&&find_circle(a[i].to,i)){
			pan[x]=1;
			if(x==st){S[0]=S[1]-a[i].w;return 0;}
			cir[++cnt]=x,S[cnt]=S[cnt-1]+a[i].w;
			return 1;
		}
	return 0;
}
inline void Tree_dp(Re x){
	pan[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan[to=a[i].to]){
			Tree_dp(to);
			tmp=max(tmp,dis[x]+a[i].w+dis[to]);
			dis[x]=max(dis[x],dis[to]+a[i].w);
		}
}
inline LL pp(Re j){return dp[j]-S[j];}
inline LL sakura(Re root){
	S[0]=cnt=st=0;find_circle(root,0);
	LL ans1=0,ans2=0;tmp=0;
	for(Re i=1;i<=cnt;++i){
		tmp=0,Tree_dp(cir[i]),ans1=max(ans1,tmp);
		dp[i+cnt]=dp[i]=dis[cir[i]];
		S[i+cnt]=S[i+cnt-1]+S[i]-S[i-1];
	}
	h=1,t=0,Q[++t]=1;//ans=max(dp[i]+dp[j]+S[i]-S[j]) i-j+1<=cnt i-cnt+1<=j<i
	for(Re i=2;i<=(cnt<<1);++i){
		while(h<=t&&Q[h]<i-cnt+1)++h;
		if(h<=t)ans2=max(ans2,dp[i]+S[i]+pp(Q[h]));
		while(h<=t&&pp(Q[t])<=pp(i))--t;
		Q[++t]=i;
	}
	return max(ans1,ans2);
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(x),in(y),add(i,x,y),add(x,i,y);
	for(Re i=1;i<=n;++i)if(!pan[i])ans+=sakura(i);
	printf("%lld",ans);
}
最近公共祖先LCA LCT
75 行
CPP JSON
【最近公共祖先LCA(LCT)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=5e5+3 说明:freopen("123.txt","r",stdin);
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,tag,ps[2];}tr[N];
	inline void pushup(Re p){}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline int access(Re p){
		Re son=0;
		for(;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
		return son;
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int lca(Re x,Re y){access(x);return access(y);}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(root),m=n-1;
	while(m--)in(x),in(y),LCT.link(x,y);LCT.makeroot(root);
	while(T--)in(x),in(y),printf("%d\n",LCT.lca(x,y));
}
最近公共祖先LCA RMQ
46 行
CPP JSON
【最近公共祖先LCA(RMQ)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void build(Re rt) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 核心结构体:QAQ, LCA 关键配置: N=5e5+3,logN=20 说明:freopen("123.txt","r",stdin);
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,logN=20;
int n,m,o,x,y,T,rt,head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int O,lg[N<<1],Qx[N<<1],Qd[N<<1],fir[N],deep[N],f[N<<1][23],ans[N<<1][23];
	inline void dfs(Re x,Re fa){
		Qx[fir[x]=++O]=x,Qd[O]=deep[x]=deep[fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dfs(to,x),Qx[++O]=x,Qd[O]=deep[x];
	}
	inline void build(Re rt){
		dfs(rt,0),lg[0]=-1;
		for(Re i=1;i<=O;++i)f[i][0]=Qd[i],ans[i][0]=Qx[i],lg[i]=lg[i>>1]+1;
		for(Re j=1;j<=logN;++j)
			for(Re i=1;i+(1<<j)-1<=O;++i)
				if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
				else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
	}
	inline int lca(Re x,Re y){
		Re L=fir[x],R=fir[y];
		if(L>R)swap(L,R);
		Re m=lg[R-L+1];
		return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(rt),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(rt);
	while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
最近公共祖先LCA 倍增
37 行
CPP JSON
【最近公共祖先LCA(倍增)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void add(Re x,Re y) — 加法更新 核心结构体:QAQ, LCA 关键配置: N=5e5+3,M=5e5+3,logN=19
C++ 36 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19;
int T,Q,n,m,x,y,o,root,head[N];
struct QAQ{int to,next;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int deep[N],ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
		if(x==y)return x;
		for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T1;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
int main(){
	in(n),in(Q),in(root),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs(root,0);
	while(Q--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
最近公共祖先LCA 树剖
51 行
CPP JSON
【最近公共祖先LCA(树剖)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void kill(Re rt) — 核心算法函数 int lca(Re x,Re y) — 查询最近公共祖先 核心结构体:Killed_Tree, QAQ 关键配置: N=5e5+3 说明:freopen("123.txt","r",stdin);
C++ 50 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Killed_Tree{
	struct QAQ{int to,next;}a[N<<1];
	int o,head[N];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	int id_o,id[N],fa[N],son[N],top[N],deep[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x);
				size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		id[x]=++id_o,top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(root),m=n-1;
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.kill(root);
	while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
树的直径 dfs
35 行
CPP JSON
【树的直径(dfs)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DFS 关键配置: N=1e4+3,M=3e5+3
C++ 34 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DFS{
	int cur,dis[N];
	inline void dfs(Re x,Re fa){
		if(dis[x]>dis[cur])cur=x;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dis[to]=dis[x]+a[i].w,dfs(to,x);
	}
	inline int sakura(){
		dfs(1,0);
		memset(dis,0,sizeof(dis));
		dfs(cur,0);
		return dis[cur];
	}
}T1;
int main(){
	in(n),m=n-1;
    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
    printf("%d\n",T1.sakura());
}
树的直径 dp
47 行
CPP JSON
【树的直径(dp)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DP1, Tree_Diam_DP2 关键配置: N=1e4+3,M=3e5+3 说明:printf("%d\n",T2.sakura());
C++ 46 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DP1{
	int ans,dis[N];
	inline void dfs(Re x,Re fa){
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x);
				ans=max(ans,dis[x]+dis[to]+a[i].w);
				dis[x]=max(dis[x],dis[to]+a[i].w);
			}
	}
	inline int sakura(){dfs(1,0);return ans;}
}T1;
struct Tree_Diam_DP2{
	int ans,dis[N][2];
	inline void dfs(Re x,Re fa){
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x);
				if(dis[x][0]<(tmp=dis[to][0]+a[i].w))dis[x][1]=dis[x][0],dis[x][0]=tmp;
				else dis[x][1]=max(dis[x][1],tmp);
			}
		ans=max(ans,dis[x][1]+dis[x][0]);
	}
	inline int sakura(){dfs(1,0);return ans;}
}T2;
int main(){
	in(n),m=n-1;
    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
    printf("%d\n",T1.sakura());
//    printf("%d\n",T2.sakura());
}
树的重心 add
42 行
CPP JSON
【树的重心】 树的重心算法模板(DFS 统计子树大小)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DP1 关键配置: N=2e4+3,inf=2e9
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2e4+3,inf=2e9;
int n,m,x,y,o,T,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DP1{
	int ans,dp[N],size[N];
	inline void dfs(Re x,Re fa){
		size[x]=1,dp[x]=0;
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x),size[x]+=size[to];
				dp[x]=max(dp[x],size[to]);
			}
		if(n-size[x])dp[x]=max(dp[x],n-size[x]);
	}
	inline void sakura(){
		dfs(1,0),dp[ans=0]=inf;
		for(Re i=1;i<=n;++i)if(dp[i]<dp[ans])ans=i;
	}
}T1;
int main(){
	in(T);
	while(T--){
		memset(head,0,sizeof(head));
		in(n),m=n-1,o=0;
	    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
	    T1.sakura();
		printf("%d %d\n",T1.ans,T1.dp[T1.ans]);
	}
}
虚树 Kingdom and its Cities
79 行
CPP JSON
【虚树(Kingdom and its Cities)】 虚树(Virtual Tree)模板,只保留关键点的压缩树。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 bool cmp(Re x,Re y) — 核心算法函数 void add(Re x,Re y) — 加法更新 void insert(Re x) — 插入元素 void dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ, LCA, Virtual_Tree, QAQ 关键配置: N=1e5+3,logN=17 说明:freopen("123.txt","r",stdin);
C++ 78 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,y,o,T,dfn_o,dfn[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][20];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1,dfn[x]=++dfn_o;
		for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re j=logN;j>=0;--j)if(deep[ant[x][j]]>=deep[y])x=ant[x][j];
		if(x==y)return x;
		for(Re j=logN;j>=0;--j)if(ant[x][j]!=ant[y][j])x=ant[x][j],y=ant[y][j];
		return ant[x][0];
	}
}T1;
inline bool cmp(Re x,Re y){return dfn[x]<dfn[y];}
struct Virtual_Tree{
	int t,o,ans,A[N],Q[N],key[N],head[N];
	struct QAQ{int to,next;}a[N<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void insert(Re x){// 撤销操作
		Re lca=T1.lca(Q[t],x);
		while(t>1&&deep[Q[t-1]]>deep[lca])add(Q[t-1],Q[t]),--t;
		if(t&&deep[Q[t]]>deep[lca])add(lca,Q[t--]);
		if(!t||Q[t]!=lca)Q[++t]=lca;
		Q[++t]=x;
	}
	inline void dfs(Re x){// 撤销操作
		if(key[x])
			for(Re i=head[x],to;i;i=a[i].next){
				dfs(to=a[i].to);
				if(key[to])key[to]=0,++ans;
			}
		else{
			for(Re i=head[x],to;i;i=a[i].next)
				dfs(to=a[i].to),key[x]+=key[to],key[to]=0;
			if(key[x]>1)key[x]=0,++ans;
		}
		head[x]=0;
	}
	inline void sakura(){
		in(m);Re flag=1;ans=o=t=0;
		for(Re i=1;i<=m;++i)in(A[i]),key[A[i]]=1;
		for(Re i=1;i<=m&&flag;++i)flag&=(!key[T1.ant[A[i]][0]]);
		if(!flag){
			for(Re i=1;i<=m;++i)key[A[i]]=0;
			puts("-1");return;
		}
		sort(A+1,A+m+1,cmp),Q[++t]=1;
		for(Re i=1+(A[1]==1);i<=m;++i)insert(A[i]);
		while(t>1)add(Q[t-1],Q[t]),--t;
		dfs(1),key[1]=0;
		printf("%d\n",ans);
	}
}T2;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs(1,0),in(T);
	while(T--)T2.sakura();
}
天天爱跑步 mid
77 行
CPP JSON
【天天爱跑步】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int merge(Re p,Re q) — 合并操作 int ask(Re p,Re L,Re R,Re x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QWQ, Segmemt_Tree, QAQ, LCA 关键配置: N=3e5+3,logN=19
C++ 76 行 CPP
#include<algorithm>
#include<cstdio>
#define pl tr[p].lp 
#define pr tr[p].rp
#define mid (L+R>>1)
#define Re register int
const int N=3e5+3,logN=19;
int x,y,n,m,T,o,lca,w[N],pt[N],ans[N],head[N],deep[N];
struct QWQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
struct Segmemt_Tree{
	struct QAQ{int g,lp,rp;}tr[N*36];int cnt;
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++cnt;
		if(L==R){tr[p].g+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
	    else change(pr,mid+1,R,x,v);
	}
	inline int merge(Re p,Re q){
	    if(!p)return q;if(!q)return p;
	    tr[p].g+=tr[q].g;
	    pl=merge(pl,tr[q].lp);
		pr=merge(pr,tr[q].rp);
	    return p;
	}
	inline int ask(Re p,Re L,Re R,Re x){
	    if(!p)return 0;
	    if(L==R)return tr[p].g;
	    if(x<=mid)return ask(pl,L,mid,x);
	    else return ask(pr,mid+1,R,x);
	}
}T1;
struct LCA{
	int ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[fa]+1,ant[x][0]=fa;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]>deep[y])std::swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
		if(x==y)return y;
		for(Re i=logN;i>=0;--i)
			if(ant[x][i]==ant[y][i])continue;
			else x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T2;
inline void dfs(Re x,Re fa){
    for(Re i=head[x],to;i;i=a[i].next)
    	if((to=a[i].to)!=fa)
        	dfs(to,x),pt[x]=T1.merge(pt[x],pt[to]);
	ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]-w[x]);
    if(w[x]&&deep[x]+w[x]<=n)ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]+w[x]);
}
int main(){
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	for(Re i=1;i<=n;++i)in(w[i]);
	T2.dfs(1,0);
	while(T--){
		in(x),in(y),lca=T2.lca(x,y);
		T1.change(pt[x],1,n<<1,n+deep[x],1);
        T1.change(pt[y],1,n<<1,n+deep[lca]*2-deep[x],1);
        T1.change(pt[lca],1,n<<1,n+deep[x],-1);
        T1.change(pt[T2.ant[lca][0]],1,n<<1,n+deep[lca]*2-deep[x],-1);
	}
	dfs(1,0);
	for(Re i=1;i<=n;++i)printf("%d ",ans[i]);
}
树的直径升级版 每个点可到的最远距离computer HDU
46 行
CPP JSON
【树的直径升级版 每个点可到的最远距离computer(HDU)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(int x,int y,int w) — 加法更新 void dfs(int x,int pa) — 深度优先搜索遍历 void dfsf(int x,int pa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ 说明:����ȹ�������ӵ�ͷ��һ���·����ô�ö��ӵķ�������������λ���׵Ĵδ���������ȡ���;����·û������ͷ����ô���ķ�������Ǹ��׵������������ȡ���
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int n,b,c,d,t,longson[10005],d1[10005],d2[10005],df[10005],head[10005];
struct QAQ{int to,next,w;}a[20005];
inline void add(int x,int y,int w){a[++t].to=y,a[t].w=w,a[t].next=head[x],head[x]=t;}
inline void dfs(int x,int pa){
	for(R i=head[x];i;i=a[i].next){
		R s,to=a[i].to;
		if(to==pa)continue;
		dfs(to,x);s=d1[to]+a[i].w;
		if(s>d1[x])d2[x]=d1[x],d1[x]=s,longson[x]=to;
		else d2[x]=max(d2[x],s);
	}
}
inline void dfsf(int x,int pa){
	for(R i=head[x];i;i=a[i].next){
		R to=a[i].to;
		if(to==pa)continue;
		if(longson[x]==to)df[to]=a[i].w+max(d2[x],df[x]);
		else df[to]=a[i].w+max(d1[x],df[x]);
		dfsf(to,x);
	}
}
inline int sakura(){
	while(~scanf("%d",&n)){
		memset(longson,0,sizeof(longson));
		memset(head,0,sizeof(head));
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		memset(df,0,sizeof(df));
		memset(a,0,sizeof(a));t=0;
		for(R i=2;i<=n;i++){
			scanf("%d%d",&b,&c);
			add(i,b,c),add(b,i,c);
		}
		dfs(1,0);dfsf(1,0);
		for(R i=1;i<=n;i++)printf("%d\n",max(d1[i],df[i]));
	}
	return 0;
}
int QAQWQ=sakura();
int main(){}
雪松果树 DFS序+分治
76 行
CPP JSON
【雪松果树(DFS序+分治)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void add(Re x,Re y,Re id) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int kant(Re x,Re k) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 核心结构体:QAQ, Query, QAQ, LCA 关键配置: N=1e6+5,logN=14 说明:freopen("123.txt","r",stdin);
C++ 75 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,dfn_O,A[N],Q[N],dfn[N],idx[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
	int o,head[N];
	struct QAQ{int to,id,next;}a[N];
	inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][15];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int kant(Re x,Re k){
		for(Re i=logN;i>=0;--i)
			if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
		return x;
	}
}T1;
inline void dfs(Re x,Re fa){
	idx[dfn[x]=++dfn_O]=x,size[x]=1,deep[x]=deep[fa]+1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void getans(Re x){
	for(Re i=QT.head[x];i;i=QT.a[i].next)
		Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
inline void sakura(Re L,Re R){
    if(L==R){if(size[idx[L]]==1)CL(),insert(idx[L]),getans(idx[L]);return;}
    Re mid=L+R>>1;
    sakura(L,mid),sakura(mid+1,R);
    Re p=mid;CL();
    for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
        insert(idx[i]);
        if(j<=mid)continue;
        while(p<j)insert(idx[++p]);
        getans(idx[i]);
    }
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=2;i<=n;++i)in(x),add(x,i);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
	dfs(1,0),sakura(1,n);
	for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
雪松果树 Dsu on tree
73 行
CPP JSON
【雪松果树(Dsu on tree)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void add(Re x,Re y,Re id) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int kant(Re x,Re k) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 核心结构体:QAQ, Query, QAQ, LCA 关键配置: N=1e6+5,logN=14 说明:freopen("123.txt","r",stdin);
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,A[N],Q[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
	int o,head[N];
	struct QAQ{int to,id,next;}a[N];
	inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][15];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int kant(Re x,Re k){
		for(Re i=logN;i>=0;--i)
			if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
		return x;
	}
}T1;
inline void dfs(Re x,Re fa){
	size[x]=1,deep[x]=deep[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x),size[x]+=size[to];
			if(size[to]>size[son[x]])son[x]=to;
		}
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
	if(son[x])sakura(son[x],x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
	insert(x);
	for(Re i=QT.head[x];i;i=QT.a[i].next)
		Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=2;i<=n;++i)in(x),add(x,i);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
	dfs(1,0),sakura(1,n);
	for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
Qtree7 LCT维护同色连通块最大点权
87 行
CPP JSON
【Qtree7(LCT维护同色连通块最大点权)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 void erase(Re x) — 删除元素 int top(无参数) — 获取栈顶/堆顶元素 void pushup(Re p) — 上推更新节点信息 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 核心结构体:QAQ, Queue, Link_Cut_Tree, QAQ 关键配置: N=1e5+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 86 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,x,y,o,T,op,A[N],co[N],fa[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Queue{
	priority_queue<int>Q,D;
	inline void insert(Re x){Q.push(x);}
	inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
	inline int top(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty()?-inf:Q.top();
	}
};
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	struct QAQ{int fa,max,ps[2];}tr[N];Queue si[N];
	inline void pushup(Re p){
		tr[p].max=max(max(A[p],si[p].top()),max(tr[pl].max,tr[pr].max));
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),si[p].insert(tr[pr].max),pr=son,si[p].erase(tr[pr].max),pushup(p);
	}
	inline void link(Re p,Re fa){
		access(p),splay(p),access(fa),splay(fa),si[pf=fa].insert(tr[p].max),pushup(fa);
	}
	inline void cut(Re p,Re fa){
		access(p),splay(p),splay(fa),pf=tr[fa].ps[1]=0,pushup(fa);
	}
	inline int ask(Re p){
		access(p),splay(p);while(pl)p=pl;splay(p);return tr[pr].max;
	}
	inline void change(Re p,Re v){
		access(p),splay(p),A[p]=v,pushup(p);
	}
}LCT[2];
inline void dfs(Re x,Re Fa){
	LCT[0].tr[x].max=LCT[1].tr[x].max=A[x];
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=Fa)dfs(to,x);
	LCT[co[x]].link(x,fa[x]=Fa);
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),m=n-1,LCT[0].tr[0].max=LCT[1].tr[0].max=-inf;
    while(m--)in(x),in(y),add(x,y),add(y,x);
    for(Re i=1;i<=n;++i)in(co[i]);
    for(Re i=1;i<=n;++i)in(A[i]);
    in(T),dfs(1,n+1);
    while(T--){
    	in(op),in(x);
    	if(op<1)printf("%d\n",LCT[co[x]].ask(x));
    	else if(op<2)LCT[co[x]].cut(x,fa[x]),LCT[co[x]^=1].link(x,fa[x]);
    	else in(y),LCT[co[x]].change(x,y);
	}
}
[RCOI] XOR (LCT 计算原树信息) TLE 30pt
96 行
CPP JSON
【[RCOI] XOR (LCT 计算原树信息)(TLE 30pt)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e6+3,M=2e6+3
C++ 95 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e6+3,M=2e6+3;
int n,m,x,y,T,op,HYJ,Ans,root,A[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,si,ans,tag,shi,yuan,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].shi=A[p]^tr[pl].shi^tr[pr].shi;
		tr[p].ans=A[p]^tr[p].si^tr[pl].ans^tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline int access(Re p){
		Re son=0;
		for(;p;son=p,p=pf)
			splay(p),tr[p].si^=tr[pr].ans,tr[p].si^=tr[pr=son].ans,pushup(p);
		return son;
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){
		makeroot(x);
		if(findroot(y)!=x)tr[tr[x].fa=y].si^=tr[x].ans,pushup(y);
	}
	inline int lca(Re x,Re y){access(x);return access(y);}
	
	inline int ask_son(Re p){access(p);return tr[pr].ans^tr[p].si^A[p];}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(HYJ),in(T),m=n-1,T+=HYJ,root=1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),LCT.link(x,y);
	LCT.makeroot(root);
//	Ans=0;for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
//	printf("%d\n",Ans);return 0;
	while(T--){
		in(op),in(x);
//		if(op<2)LCT.makeroot(root=x),printf("%d\n",Ans);
		if(op<2){
			LCT.makeroot(root=x);Ans=0;
			for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
			printf("%d\n",Ans);
		}
		else if(op<3)in(y),LCT.access(x),LCT.splay(x),A[x]=y,LCT.pushup(x);
		else if(op<4)in(y),printf("%d\n",LCT.lca(x,y));
		else if(op<5)in(y),LCT.split(x,y),printf("%d\n",LCT.tr[y].shi),LCT.makeroot(root);
		else printf("%d\n",LCT.ask_son(x));
		LCT.makeroot(root);
	}
}
LCT 动态树 pushup
80 行
CPP JSON
【LCT 动态树】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 79 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T,op,a[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,ans,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].ans=a[p]^tr[pl].ans^tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(a[i]);
	while(T--){
		in(op),in(x),in(y);
		if(!op)LCT.split(x,y),printf("%d\n",LCT.tr[y].ans);
		else if(op<2)LCT.link(x,y);
		else if(op<3)LCT.cut(x,y);
		else LCT.splay(x),a[x]=y,LCT.pushup(x);
	}
}
动态DP (带修树上最大点权独立集) LCT
84 行
CPP JSON
【动态DP (带修树上最大点权独立集)(LCT)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) void splay(Re p) — 伸展操作(Splay树) 核心结构体:QAQ, Matrix, Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 83 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
	inline Mat operator*(const Mat &O)const{
		Mat A;
		for(Re i=1;i<=2;++i)
			for(Re j=1;j<=2;++j)
				for(Re k=1;k<=2;++k)
					A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
		return A;
	}
}G[N];
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	struct QAQ{int fa,ps[2];}tr[N];Mat TR[N];
	inline void pushup(Re p){
		TR[p]=G[p];
		if(pl)TR[p]=TR[pl]*TR[p];
		if(pr)TR[p]=TR[p]*TR[pr];
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf){
			splay(p);
			if(pr)G[p].a[1][1]+=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]+=TR[pr].a[1][1];
			pr=son;
			if(pr)G[p].a[1][1]-=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]-=TR[pr].a[1][1];
			pushup(p);
		}
	}
	inline void change(Re x,Re v){access(x),splay(x),G[x].a[2][1]+=v-A[x],A[x]=v,pushup(x);}//�޸�x�ĵ�Ȩ(G[x][1])
	inline LL ask(){splay(1);return max(TR[1].a[1][1],TR[1].a[2][1]);}
}T1;
LL g[N][2];
inline void dfs(Re x,Re fa){
	g[x][1]=A[x],T1.tr[x].fa=fa;
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
		dfs(to,x),g[x][0]+=max(g[to][0],g[to][1]),g[x][1]+=g[to][0];
	G[x].a[1][1]=G[x].a[1][2]=g[x][0];
	G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
	T1.pushup(x);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0);
	while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
动态DP (带修树上最大点权独立集) 树剖
99 行
CPP JSON
【动态DP (带修树上最大点权独立集)(树剖)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re x,Mat &v) — 核心算法函数 Mat ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 核心结构体:QAQ, Matrix, killed_Tree, Segment_Tree 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 98 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
	inline Mat operator*(const Mat &O)const{
		Mat A;
		for(Re i=1;i<=2;++i)
			for(Re j=1;j<=2;++j)
				for(Re k=1;k<=2;++k)
					A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
		return A;
	}
}G[N];
int idx[N];
struct killed_Tree{
	struct Segment_Tree{
		#define pl (p<<1)
		#define pr (p<<1|1)
		#define mid ((L+R)>>1)
		Mat tr[N<<2];
		inline void pushup(Re p){tr[p]=tr[pl]*tr[pr];}
		inline void build(Re p,Re L,Re R){
			if(L==R){tr[p]=G[idx[L]];return;}
			build(pl,L,mid),build(pr,mid+1,R);
			pushup(p);
		}
		inline void change(Re p,Re L,Re R,Re x,Mat &v){
			if(L==R){tr[p]=v;return;}
			if(x<=mid)change(pl,L,mid,x,v);
			else change(pr,mid+1,R,x,v);
			pushup(p);
		}
		inline Mat ask(Re p,Re L,Re R,Re l,Re r){
			if(l<=L&&R<=r)return tr[p];
			if(r<=mid)return ask(pl,L,mid,l,r);
			else if(l>mid)return ask(pr,mid+1,R,l,r);
			else return ask(pl,L,mid,l,r)*ask(pr,mid+1,R,l,r);
		}
	}TR;
	int id_O,fa[N],st[N],ed[N],son[N],top[N],deep[N],size[N];LL f[N][2],g[N][2];
	inline void dfs1(Re x,Re Fa){
		deep[x]=deep[fa[x]=Fa]+1,size[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		idx[st[x]=++id_O]=x,ed[rt]=max(ed[rt],id_O),top[x]=rt;
		f[x][0]=g[x][0]=0,f[x][1]=g[x][1]=A[x];
		if(son[x])dfs2(son[x],rt),f[x][0]+=max(f[son[x]][0],f[son[x]][1]),f[x][1]+=f[son[x]][0];
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x]){
				dfs2(to,to);
				f[x][0]+=max(f[to][0],f[to][1]),f[x][1]+=f[to][0];
				g[x][0]+=max(f[to][0],f[to][1]),g[x][1]+=f[to][0];
			}
		G[x].a[1][1]=G[x].a[1][2]=g[x][0];
		G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
	}
	inline LL ask(){Mat F=TR.ask(1,1,n,st[1],ed[1]);return max(F.a[1][1],F.a[2][1]);}
	inline void change(Re x,Re v){//�޸�x�ĵ�Ȩ
		G[x].a[2][1]+=v-A[x],A[x]=v;//�޸�G[x][1]
		while(x){
			Mat F1=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
			TR.change(1,1,n,st[x],G[x]);
			Mat F2=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
			x=fa[top[x]];
			G[x].a[1][1]+=max(F2.a[1][1],F2.a[2][1])-max(F1.a[1][1],F1.a[2][1]),G[x].a[1][2]=G[x].a[1][1];
			G[x].a[2][1]+=F2.a[1][1]-F1.a[1][1];
		}
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs1(1,0),T1.dfs2(1,1),T1.TR.build(1,1,n);
	while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
大融合 LCT 计算虚子树信息
81 行
CPP JSON
【大融合(LCT 计算虚子树信息)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 80 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T;char op;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,si,ans,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].ans=1+tr[p].si+tr[pl].ans+tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),tr[p].si+=tr[pr].ans,tr[p].si-=tr[pr=son].ans,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){
		makeroot(x);
		if(findroot(y)!=x)tr[tr[x].fa=y].si+=tr[x].ans,pushup(y);
	}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int ask(Re x,Re y){split(x,y);return (tr[x].si+1)*(tr[y].si+1);}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	while(T--){
		scanf(" %c",&op),in(x),in(y);
		if(op=='A')LCT.link(x,y);
		if(op=='Q')printf("%d\n",LCT.ask(x,y));
	}
}
树链剖分 重链剖分
110 行
CPP JSON
【树链剖分(重链剖分)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void pushdown(Re p) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re l,Re r,Re v) — 核心算法函数 int ask(Re p,Re l,Re r) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 核心结构体:Killed_Tree, QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3
C++ 109 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,z,T,P,op,root,A[N],AA[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Killed_Tree{
	struct QAQ{int to,next;}a[N<<1];
	int o,id_o,fa[N],id[N],idx[N],top[N],son[N],size[N],deep[N],head[N];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	struct Segment_Tree{
		#define pl (p<<1)
		#define pr (p<<1|1)
		#define mid (L+R>>1)
		struct QAQ{int S,l,r,add;}tr[N<<2];
		inline void pushdown(Re p){
			Re v=tr[p].add;
			if(v){
				(tr[pl].S+=v*(tr[pl].r-tr[pl].l+1)%P)%=P,(tr[pl].add+=v)%=P;
				(tr[pr].S+=v*(tr[pr].r-tr[pr].l+1)%P)%=P,(tr[pr].add+=v)%=P;
				tr[p].add=0;
			}
		}
		inline void build(Re p,Re L,Re R){
			tr[p].l=L,tr[p].r=R;
			if(L==R){tr[p].S=AA[L]%P;return;}
			build(pl,L,mid),build(pr,mid+1,R);
			tr[p].S=(tr[pl].S+tr[pr].S)%P;
		}
		inline void change(Re p,Re l,Re r,Re v){
			Re L=tr[p].l,R=tr[p].r;
			if(l<=L&&R<=r){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;return;}
			pushdown(p);
			if(l<=mid)change(pl,l,r,v);
			if(r>mid)change(pr,l,r,v);
			tr[p].S=(tr[pl].S+tr[pr].S)%P;
		}
		inline int ask(Re p,Re l,Re r){
			Re L=tr[p].l,R=tr[p].r;
			if(l<=L&&R<=r)return tr[p].S;
			Re ans=0;pushdown(p);
			if(l<=mid)(ans+=ask(pl,l,r))%=P;
			if(r>mid)(ans+=ask(pr,l,r))%=P;
			return ans;
		}
	}TR;
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x);
				size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		id[x]=++id_o,idx[id_o]=x,AA[id_o]=A[x],top[x]=rt;
		if(!son[x])return;//Ҷ�ڵ�
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt),TR.build(1,1,n);}
	inline int ask_dis(Re x,Re y){
		Re ans=0;
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			(ans+=TR.ask(1,id[top[x]],id[x]))%=P;
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		(ans+=TR.ask(1,id[x],id[y]))%=P;
		return ans;
	}
	inline void change_dis(Re x,Re y,Re v){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			TR.change(1,id[top[x]],id[x],v);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		TR.change(1,id[x],id[y],v);
	}
	inline int ask_son(Re x){
		return TR.ask(1,id[x],id[x]+size[x]-1);
	}
	inline void change_son(Re x,Re v){
		TR.change(1,id[x],id[x]+size[x]-1,v);
	}
}T1;
int main(){
	in(n),in(T),in(root),in(P),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.kill(root);
	while(T--){
		in(op);
		if(op<2)in(x),in(y),in(z),T1.change_dis(x,y,z%P);
		else if(op<3)in(x),in(y),printf("%d\n",T1.ask_dis(x,y));
		else if(op<4)in(x),in(z),T1.change_son(x,z%P);
		else in(x),printf("%d\n",T1.ask_son(x));
	}
}
水管局长 LCT动态维护MST
109 行
CPP JSON
【水管局长(LCT动态维护MST)】 树上问题算法模板。 核心函数: void in(int &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Query, Link_Cut_Tree, QAQ, Kruscal, QAQ 关键配置: N=1003,M=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 108 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=1e5+3;
int n,m,x,y,z,T,op,id,id_O,v[N+M],vis[N+M],Ans[M],ID[N][N];
struct Query{int op,x,y;}Q[M];
inline void in(int &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N+M];
	struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
	inline void pushup(Re p){
		tr[p].mx=p;
		if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
		if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p); 
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re x){access(x),splay(x),updata(x);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline void MST_link(Re x,Re y,Re id){
		makeroot(x);
		if(findroot(y)!=x)link(x,id),link(id,y);
		else{
			split(x,y);Re mx=tr[y].mx;
			if(v[id]<v[mx]){
				splay(mx);
				tr[tr[mx].ps[0]].fa=tr[tr[mx].ps[1]].fa=0;
				tr[mx].ps[0]=tr[mx].ps[1]=tr[mx].fa=0;
				link(x,id),link(id,y);
			}
		}
	}
	inline int MST_path(Re x,Re y){split(x,y);return v[tr[y].mx];}
}LCT;
struct Kruscal{
	int fa[N];
	struct QAQ{int x,y,z;inline bool operator<(const QAQ &O)const{return z<O.z;}}a[M];
	inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
	inline void sakura(){
		for(Re i=1;i<=n;++i)fa[i]=i;
		for(Re i=1;i<=m;++i)in(x),in(y),in(z),v[ID[x][y]=ID[y][x]=++id_O+n]=z,a[i]=(QAQ){x,y,z};
		for(Re i=1;i<=T;++i)in(op),in(x),in(y),vis[ID[x][y]]|=op>1,Q[i]=(Query){op,x,y};
		sort(a+1,a+m+1);
		for(Re i=1,t=0;t<n-1&&i<=m;++i)
			if(!vis[ID[x=a[i].x][y=a[i].y]]&&find(x)!=find(y))
				fa[find(x)]=find(y),++t,LCT.MST_link(x,y,ID[x][y]);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(T),T1.sakura();
	for(Re i=T;i>=1;--i){
		Re op=Q[i].op,x=Q[i].x,y=Q[i].y;
		if(op&1)Ans[++Ans[0]]=LCT.MST_path(x,y);
		else LCT.MST_link(x,y,ID[x][y]);
	}
	for(Re i=Ans[0];i>=1;--i)printf("%d\n",Ans[i]);
}
遥远的国度 LCT维护原子树信息
88 行
CPP JSON
【遥远的国度(LCT维护原子树信息)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void updata(Re p,Re v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3,inf=2e9 说明:shi: ����ʵ����(�ڸ����ϵ�v);si: ���������������(���ڸ����ϵ�ans);freopen("123.txt","r",stdin);
C++ 87 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,x,y,z,T,op,root,X[N],Y[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	#define pv tr[p].v
	int Q[N];
	struct QAQ{int v,fa,si,shi,ans,add,tag,ans0,ps[2];multiset<int>SI;}tr[N];
	inline void pushup(Re p){
		tr[p].shi=min(pv,min(tr[pl].shi,tr[pr].shi));
		tr[p].si=min(*tr[p].SI.begin(),min(tr[pl].si,tr[pr].si));
		tr[p].ans=min(tr[p].shi,tr[p].si);
	}
	inline void updata(Re p){tr[p].tag^=1,swap(pl,pr);}
	inline void updata(Re p,Re v){tr[p].add=1,tr[p].shi=pv=v,tr[p].ans=min(tr[p].shi,tr[p].si);}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
		if(tr[p].add){
			if(pl)updata(pl,pv);
			if(pr)updata(pr,pv);
			tr[p].add=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf){
			splay(p);
			if(pr)tr[p].SI.insert(tr[pr].ans);
			pr=son;
			if(pr)tr[p].SI.erase(tr[p].SI.lower_bound(tr[pr].ans));
			pushup(p);
		}
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline void link(Re x,Re y){makeroot(x),access(y),splay(y),tr[tr[x].fa=y].SI.insert(tr[x].ans);}
	inline void change(Re x,Re y,Re z){makeroot(x),access(y),splay(y),updata(y,z);}
	inline int ask_son(Re p){access(p),splay(p);return min(pv,*tr[p].SI.begin());}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),T1.tr[0].shi=T1.tr[0].si=inf;
	for(Re i=1;i<n;++i)in(X[i]),in(Y[i]);
	for(Re i=1;i<=n;++i)in(T1.tr[i].v),T1.tr[i].SI.insert(inf),T1.pushup(i);
	for(Re i=1;i<n;++i)T1.link(X[i],Y[i]);
	in(root),T1.makeroot(root);
	while(T--){
		in(op),in(x);
		if(op<2)T1.makeroot(root=x);
		else if(op<3)in(y),in(z),T1.change(x,y,z),T1.makeroot(root);
		else printf("%d\n",T1.ask_son(x));
	}
}
长链剖分优化dp Dominant Indices
46 行
CPP JSON
【长链剖分优化dp(Dominant Indices)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=1e6+3 说明:freopen("123.txt","r",stdin);
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3;
int n,m,x,y,o,Sz[N],son[N],Ans[N],dep[N],head[N];int *SZ=Sz,*dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs1(to,x);
			if(dep[to]>dep[son[x]])son[x]=to;
		}
	dep[x]=dep[son[x]]+1;
}
inline void dfs2(Re x,Re fa){
	dp[x][0]=1;
	if(son[x])dp[son[x]]=dp[x]+1,dfs2(son[x],x),Ans[x]=Ans[son[x]]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x]){
			dp[to]=SZ,SZ+=dep[to],dfs2(to,x);
			for(Re j=1;j<=dep[to];++j){
				dp[x][j]+=dp[to][j-1];
				if(dp[x][j]>dp[x][Ans[x]])Ans[x]=j;
				else if(dp[x][j]==dp[x][Ans[x]])Ans[x]=min(Ans[x],j);
			}
		}
	if(dp[x][Ans[x]]==1)Ans[x]=0;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs1(1,0),dp[1]=SZ,SZ+=dep[1],dfs2(1,0);
	for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
Distance in Tree 长度等于K的路径数
58 行
CPP JSON
【Distance in Tree(长度等于K的路径数)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa) — 获取值 int calc(Re x,Re d) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=5e4+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,inf=2e9;
int n,m,o,x,y,K,head[N];LL Ans;
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa){
	if(dis[fa]+1>K)return;
	tmp[++cnt]=dis[x]=dis[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x);
}
inline int calc(Re x,Re d){
	Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])getdis(to,x);
	sort(tmp+1,tmp+cnt+1);
	Re L=cnt+1,R=cnt;
	for(Re i=1;i<=cnt&&i<R;++i){
		while(tmp[i]+tmp[L-1]>=K)--L;
		while(R>=L&&tmp[i]+tmp[R]>K)--R;
		if(L<=R&&i<R&&tmp[i]+tmp[L]==K&&tmp[i]+tmp[R]==K)ans+=(R-max(L,i+1)+1);
	}
	return ans;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,Ans+=calc(x,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			Ans-=calc(to,1),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%lld\n",Ans);
}
Qtree4 点分树+可删堆
124 行
CPP JSON
【Qtree4(点分树+可删堆)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa,Re w) — 深度优先搜索遍历 void build(Re rt) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 int top(无参数) — 获取栈顶/堆顶元素 int sec(无参数) — 核心算法函数 核心结构体:QAQ, LCA, Queue 关键配置: N=1e5+3,logN=18,inf=1e9 说明:freopen("123.txt","r",stdin);
C++ 123 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18,inf=1e9;
int n,m,x,y,z,o,T,Cnt,A[N],ans[N],head[N];char op;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int O,lg[N<<1],fir[N],idx[N<<1],idd[N<<1],dis[N],deep[N],f[N<<1][20],ans[N<<1][20];
	inline void dfs(Re x,Re fa,Re w){
		idx[fir[x]=++O]=x,idd[O]=deep[x]=deep[fa]+1,dis[x]=dis[fa]+w;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dfs(to,x,a[i].w),idx[++O]=x,idd[O]=deep[x];
	}
	inline void build(Re rt){
		dfs(rt,0,0),lg[0]=-1;
		for(Re i=1;i<=O;++i)f[i][0]=idd[i],ans[i][0]=idx[i],lg[i]=lg[i>>1]+1;
		for(Re j=1;j<=logN;++j)
			for(Re i=1;i+(1<<j)-1<=O;++i)
				if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
				else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
	}
	inline int lca(Re x,Re y){
		Re L=fir[x],R=fir[y];
		if(L>R)swap(L,R);
		Re m=lg[R-L+1];
		return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
	}
}T0;
inline int Dis(Re x,Re y){return T0.dis[x]+T0.dis[y]-(T0.dis[T0.lca(x,y)]<<1);}
struct Queue{
	priority_queue<int>Q,D;
	inline int top(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty()?-inf:Q.top();
	}
	inline int sec(){
		Re x=top();if(x==-inf)return x;
		Q.pop();Re ans=top();Q.push(x);
		return ans;
	}
	inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
	inline void insert(Re x){Q.push(x);}
	inline int empty(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty();
	}
}Ans,Q[N],dis[N];
int rt,sum,Fa[N],vis[N],size[N],maxp[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re rt){
	dis[rt].insert(Dis(x,Fa[rt]));
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,rt);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,0,x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0);
			Fa[to=rt]=x,sakura(rt),Q[x].insert(dis[to].top());
		}
	Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
}
inline void insert(Re x){
	Ans.erase(ans[x]),Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
	for(Re fa=x;Fa[fa];fa=Fa[fa]){
		Re pa=Fa[fa];
		Ans.erase(ans[pa]);
		if(!dis[fa].empty())Q[pa].erase(dis[fa].top());
		
		dis[fa].insert(Dis(x,pa));
		
		Q[pa].insert(dis[fa].top());
		Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
	}
}
inline void erase(Re x){
	Ans.erase(ans[x]),Q[x].erase(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
	for(Re fa=x;Fa[fa];fa=Fa[fa]){
		Re pa=Fa[fa];
		Ans.erase(ans[pa]);
		Q[pa].erase(dis[fa].top());
		
		dis[fa].erase(Dis(x,pa));
		
		if(!dis[fa].empty())Q[pa].insert(dis[fa].top());
		Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
	}
}
inline void change(Re x){
	if(A[x])insert(x),A[x]=0,++Cnt;
	else erase(x),A[x]=1,--Cnt;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1,Cnt=n;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	in(T),T0.build(1),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	while(T--){
		scanf(" %c",&op);
		if(op=='C')in(x),change(x);
		else if(!Cnt)puts("They have disappeared.");
		else printf("%d\n",Cnt<2?0:Ans.top());
	}
}
Race 长度等于K的路径最小边数
56 行
CPP JSON
【Race(长度等于K的路径最小边数)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 void calc(Re x) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=2e5+3,INF=1e6+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,INF=1e6+3,inf=2e9;
int n,m,o,x,y,z,K,Ans,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,dd[N],ddd[N],dep[N],Min[INF],tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>K)return;
	dd[++dd[0]]=dis[x]=dis[fa]+w,ddd[dd[0]]=dep[x]=dep[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
	dis[x]=dep[x]=tmp[0]=0,Min[tmp[++tmp[0]]=0]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			dd[0]=0,getdis(to,x,a[i].w);
			for(Re i=1;i<=dd[0];++i)Ans=min(Ans,ddd[i]+Min[K-dd[i]]);
			for(Re i=1;i<=dd[0];++i)Min[dd[i]]=min(Min[dd[i]],ddd[i]),tmp[++tmp[0]]=dd[i];
		}
	for(Re i=1;i<=tmp[0];++i)Min[tmp[i]]=inf;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,calc(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	for(Re i=0;i<=K;++i)Min[i]=inf;
	while(m--)in(x),in(y),in(z),++x,++y,add(x,y,z),add(y,x,z);
	Ans=inf,sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%d\n",(Ans==inf)?-1:Ans);
}
点分树-在线求原树距离-BIT 求距离小于等于K的点权值之和 震波
98 行
CPP JSON
【点分树-在线求原树距离-BIT(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 void build(Re N) — 构建数据结构(建树/建图) 核心结构体:QAQ, LCA, BIT 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 97 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int fa[N],top[N],son[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[son[x]]<size[to])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void build(){dfs1(1,0),dfs2(1,1);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
struct BIT{
	int n;vector<int>C;
	inline void build(Re N){C.resize((n=N)+1);}
	inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
	Re now=sum;vis[x]=1,fa[x]=Fa;
	TR1[x].build(now/2+1),TR2[x].build(now+1);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
	TR1[x].add(0,v);//subtree(x)
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);
		TR1[fa[i]].add(tmp,v);
		TR2[i].add(tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR1[x].ask(K);//subtree(x)
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
		ans+=TR1[fa[i]].ask(K-tmp);
		ans-=TR2[i].ask(K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-在线求原树距离-Seg 求距离小于等于K的点权值之和 震波
113 行
CPP JSON
【点分树-在线求原树距离-Seg(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 核心结构体:QAQ, LCA, Segment_Tree, QAQ 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 112 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int fa[N],top[N],son[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[son[x]]<size[to])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void build(){dfs1(1,0),dfs2(1,1);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
int pt[N<<1];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid (L+R>>1)
	int O;
	struct QAQ{int S,lp,rp;}tr[N*60];
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].S+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		tr[p].S=tr[pl].S+tr[pr].S;
	}
	inline int ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		Re ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
}TR;
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
	Re now=sum;vis[x]=1,fa[x]=Fa;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
	TR.change(pt[x],0,n,0,v);
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);
		TR.change(pt[fa[i]],0,n,tmp,v);
		TR.change(pt[i+n],0,n,tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR.ask(pt[x],0,n,0,K);
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
		ans+=TR.ask(pt[fa[i]],0,n,0,K-tmp);
		ans-=TR.ask(pt[i+n],0,n,0,K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-预处理原树距离-BIT 求距离小于等于K的点权值之和 震波
75 行
CPP JSON
【点分树-预处理原树距离-BIT(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void build(Re N) — 构建数据结构(建树/建图) void add(Re x,Re v) — 加法更新 int ask(Re x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 核心结构体:QAQ, BIT 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
	int n;vector<int>C;
	inline void build(Re N){C.resize((n=N)+1);}
	inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	TR1[x].build(now/2+1),TR2[x].build(now+1);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
	TR1[x].add(0,v);//subtree(x)
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		TR1[frt[x][i-1]].add(tmp,v);
		TR2[frt[x][i]].add(tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR1[x].ask(K);//subtree(x)
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];if(tmp>K)continue;
		ans+=TR1[frt[x][i-1]].ask(K-tmp);
		ans-=TR2[frt[x][i]].ask(K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-预处理原树距离-Seg 求距离小于等于K的点权值之和 震波
90 行
CPP JSON
【点分树-预处理原树距离-Seg(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 void change(Re x,Re v) — 核心算法函数 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 89 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid (L+R>>1)
	int O;
	struct QAQ{int S,lp,rp;}tr[N*60];
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].S+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		tr[p].S=tr[pl].S+tr[pr].S;
	}
	inline int ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		Re ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
}TR;
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
	TR.change(pt[x],0,n,0,v);
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		TR.change(pt[frt[x][i-1]],0,n,tmp,v);
		TR.change(pt[frt[x][i]+n],0,n,tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR.ask(pt[x],0,n,0,K);
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];if(tmp>K)continue;
		ans+=TR.ask(pt[frt[x][i-1]],0,n,0,K-tmp);
		ans-=TR.ask(pt[frt[x][i]+n],0,n,0,K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分治 (询问是否有长度等于K的路径) 分各子树求解
58 行
CPP JSON
【点分治 (询问是否有长度等于K的路径)(分各子树求解)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 void calc(Re x) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=1e4+3,M=103,INF=1e7+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e4+3,M=103,INF=1e7+3,inf=2e9;
int n,m,o,x,y,z,T,maxK,K[M],Ans[M],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,dd[N],vis[N],tmp[N],dis[N],maxp[N],size[N];bool judge[INF];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>maxK)return;
	dd[++dd[0]]=dis[x]=dis[fa]+w;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
	tmp[0]=0,judge[tmp[++tmp[0]]=0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			dis[x]=dd[0]=0,getdis(to,x,a[i].w);
			for(Re j=1;j<=dd[0];++j)
				for(Re k=1;k<=T;++k)
					if(K[k]>=dd[j])Ans[k]|=judge[K[k]-dd[j]];
			for(Re j=1;j<=dd[0];++j)judge[tmp[++tmp[0]]=dd[j]]=1;
		}
	for(Re i=1;i<=tmp[0];++i)judge[tmp[i]]=0;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,calc(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	for(Re i=1;i<=T;++i)in(K[i]),maxK=max(maxK,K[i]);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=T;++i)puts(Ans[i]?"AYE":"NAY");
}
点分治 (长度小于等于K的路径数 Tree) 容斥
58 行
CPP JSON
【点分治 (长度小于等于K的路径数 Tree)(容斥)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 int calc(Re x,Re d) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=4e4+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,inf=2e9;
int n,m,o,x,y,z,K,head[N];LL Ans;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>K)return;
	tmp[++cnt]=dis[x]=dis[fa]+w;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline int calc(Re x,Re d){
	Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])getdis(to,x,a[i].w);
	sort(tmp+1,tmp+cnt+1);
	Re R=cnt;
	for(Re i=1;i<=cnt&&i<R;++i){
		while(i<R&tmp[i]+tmp[R]>K)--R;
		if(i<R)ans+=(R-(i+1)+1);
	}
	return ans;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,Ans+=calc(x,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			Ans-=calc(to,a[i].w),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	in(K);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%lld\n",Ans);
}
幻想乡战略游戏 点分树
76 行
CPP JSON
【幻想乡战略游戏(点分树)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 void change(Re x,Re v) — 核心算法函数 LL ask(Re x) — 核心算法函数 核心结构体:QAQ, TREE, QAQ 关键配置: N=1e5+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 75 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,o,x,y,z,T,root,A[N],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct TREE{
	int o,head[N];
	struct QAQ{int rt,to,next;}a[N];
	inline void add(Re x,Re y,Re z){a[++o].rt=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
}T0;
int rt,sum,Sv[N],gs[N],vis[N],size[N],maxp[N],frt[N][20],fdis[N][20];LL Sdv1[N],Sdv2[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	if(x!=rt)frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+a[i].w);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),T0.add(x,to,rt),sakura(rt);
}
inline void change(Re x,Re v){
	Sdv1[x]+=v*0,Sv[x]+=v;
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		Sdv1[frt[x][i-1]]+=(LL)v*tmp;
		Sdv2[frt[x][i]]+=(LL)v*tmp;
		Sv[frt[x][i-1]]+=v;
	}
}
inline LL ask(Re x){
	LL ans=Sdv1[x];
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		ans+=Sdv1[frt[x][i-1]];
		ans-=Sdv2[frt[x][i]];
		ans+=(LL)(Sv[frt[x][i-1]]-Sv[frt[x][i]])*tmp;
	}
	return ans;
}
inline LL find(Re x){
	LL tmp=ask(x);
	for(Re i=T0.head[x];i;i=T0.a[i].next)
		if(ask(T0.a[i].to)<tmp)return find(T0.a[i].rt);
	return tmp;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(root=rt);
	for(Re i=1;i<=n;++i)frt[i][++gs[i]]=i;
	while(T--)in(x),in(y),change(x,y),printf("%lld\n",find(root));
}
已复制