本文共 3577 字，大约阅读时间需要 11 分钟。

写个树链剖分练练手

挺常规的树链剖分，注意这个线段树维护的是每个节点的权值，而不是原图中边的权值，在处理的时候注意一下处理边界就能A了

还有一些小的注意事项详细看注释

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 30010#define INF 0x7f7f7f7f#define LEFT (pos << 1)#define RIGHT (pos << 1|1)using namespace std;const char qmax[10] = "QMAX";const char qsum[10] = "QSUM";const char change[10] = "CHANGE";struct Complex{	int _max,sum;}tree[MAX << 2];int points,asks;int head[MAX],total;int _next[MAX << 1],aim[MAX << 1];int deep[MAX],father[MAX],son[MAX];					//PreDFS处理的数组int top[MAX],p[MAX],cnt;						//DFS处理的数组char s[10];inline void Add(int x,int y);int PreDFS(int x,int last,int step);void DFS(int x,int last,int t);void Modify(int l,int r,int x,int pos,int num);inline int AskMax(int x,int y);int AskMax(int l,int r,int x,int y,int pos);inline int AskSum(int x,int y);int AskSum(int l,int r,int x,int y,int pos);		
       		//函数的重载，如果用的话一定要看清楚，别把函数调用错了int main(){	cin >> points;	for(int x,y,i = 1;i < points; ++i) {		scanf("%d%d",&x,&y);		Add(x,y),Add(y,x);	}	PreDFS(1,-1,1);	DFS(1,-1,1);	for(int x,i = 1;i <= points; ++i) {		scanf("%d",&x);		Modify(1,cnt,p[i],1,x);	}	cin >> asks;	for(int x,y,i = 1;i <= asks; ++i) {		scanf("%s%d%d",s,&x,&y);		if(!strcmp(s,qmax))			printf("%d\n",AskMax(x,y));		if(!strcmp(s,qsum))			printf("%d\n",AskSum(x,y));		if(!strcmp(s,change))			Modify(1,cnt,p[x],1,y);	}	return 0;}inline void Add(int x,int y){	_next[++total] = head[x];	aim[total] = y;	head[x] = total;}int PreDFS(int x,int last,int step){	int max_size = 0,p_son = 0,re = 1;					//这里re＝1，每次写都忘记，然后调试出来……千万要记住啊	father[x] = last;	deep[x] = step;	for(int i = head[x];i;i = _next[i]) {		if(aim[i] == last)	continue;		int temp = PreDFS(aim[i],x,step + 1);        re += temp;		if(temp > max_size)			max_size = temp,p_son = aim[i];	}	son[x] = p_son;    return re;}void DFS(int x,int last,int t){	p[x] = ++cnt;	top[x] = t;	if(son[x])	DFS(son[x],x,t);	for(int i = head[x];i;i = _next[i]) {		if(aim[i] == last || aim[i] == son[x])	continue;		DFS(aim[i],x,aim[i]);	}}void Modify(int l,int r,int x,int pos,int num){	if(l == r && l == x) {		tree[pos].sum = tree[pos]._max = num;		return ;	}	int mid = (l + r) >> 1;	if(x <= mid)	Modify(l,mid,x,LEFT,num);	else 	Modify(mid + 1,r,x,RIGHT,num);	tree[pos].sum = tree[LEFT].sum + tree[RIGHT].sum;	tree[pos]._max = max(tree[LEFT]._max,tree[RIGHT]._max);	}inline int AskMax(int x,int y){	int re = -INF;					//注意这里的初值	int fx = top[x],fy = top[y];	while(fx != fy) {		if(deep[fx] < deep[fy])			swap(fx,fy),swap(x,y);		re = max(re,AskMax(1,cnt,p[fx],p[x],1));		x = father[fx];		fx = top[x];	}    if(deep[x] < deep[y])	swap(x,y);    re = max(re,AskMax(1,cnt,p[y],p[x],1));	return re;}int AskMax(int l,int r,int x,int y,int pos){	if(l == x && r == y)		return tree[pos]._max;	int mid = (l + r) >> 1;	if(y <= mid)	return AskMax(l,mid,x,y,LEFT);	if(x > mid)	return AskMax(mid + 1,r,x,y,RIGHT);	int left = AskMax(l,mid,x,mid,LEFT);	int right = AskMax(mid + 1,r,mid + 1,y,RIGHT);	return max(left,right);}inline int AskSum(int x,int y){	int re = 0;	int fx = top[x],fy = top[y];	while(fx != fy) {		if(deep[fx] < deep[fy])			swap(fx,fy),swap(x,y);		re += AskSum(1,cnt,p[fx],p[x],1);		x = father[fx];		fx = top[x];	}    if(deep[x] < deep[y])	swap(x,y);    re += AskSum(1,cnt,p[y],p[x],1);	return re;}int AskSum(int l,int r,int x,int y,int pos){	if(l == x && r == y)		return tree[pos].sum;	int mid = (l + r) >> 1;	if(y <= mid)	return AskSum(l,mid,x,y,LEFT);	if(x > mid)		return AskSum(mid + 1,r,x,y,RIGHT);	int left = AskSum(l,mid,x,mid,LEFT);	int right = AskSum(mid + 1,r,mid + 1,y,RIGHT);	return left + right;}
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/38932257 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！