题意：给一棵树，三种操作。将第i条边的权值改为v，将a到b的路径上的边的权值全部取反，求a到b路径上边的权值的最大值。

思路：明显的树链剖分，加上线段树的操作。因为有取反的操作所以每个区间要记录最大值和最小值。查询两点间的路径时，用求公共祖先的方式去求。

 

#include
    
     #include
     
      #include
      
       const int N=101000;const int inf=0x3fffffff;using namespace std;int head[N],num,son[N],sz[N],father[N],dep[N],idx,a[N],cot[N],ti[N],top[N];struct edge{	int st,ed,w,next;}e[N*4];void addedge(int x,int y,int w){	e[num].st=x;e[num].ed=y;e[num].w=w;e[num].next=head[x];head[x]=num++;	e[num].st=y;e[num].ed=x;e[num].w=w;e[num].next=head[y];head[y]=num++;}int max(int a,int b){	if(a>b)return a;	return b;}int min(int a,int b){	if(a>b)return b;	return a;}//******************树链剖分****************************void find_son(int u,int fa){	int i,v;	son[u]=0;sz[u]=1;	for(i=head[u];i!=-1;i=e[i].next)	{		v=e[i].ed;		if(v==fa)continue;		father[v]=u;		dep[v]=dep[u]+1;		a[v]=e[i].w;		find_son(v,u);		sz[u]+=sz[v];		if(sz[v]>sz[son[u]])son[u]=v;	}}void find_time(int u,int fa){	int i,v;	ti[u]=idx++;	cot[ti[u]]=a[u];	top[u]=fa;	if(son[u]!=0)find_time(son[u],top[u]);	for(i=head[u];i!=-1;i=e[i].next)	{		v=e[i].ed;		if(v==son[u]||v==father[u])continue;		find_time(v,v);	}}//***********************线段树*********************struct Tree{	int L,R,Mw,mw;	int flag;//该区间是否取反}T[N*10];void up(int id){	int li=id<<1,ri=li|1;    T[id].Mw=max(T[li].Mw,T[ri].Mw);	T[id].mw=min(T[li].mw,T[ri].mw);}void buildTree(int L,int R,int id){	T[id].L=L;T[id].R=R;T[id].flag=0;	if(L==R)	{		T[id].Mw=T[id].mw=cot[L];		return;	}	int mid=(L+R)>>1,li=id<<1,ri=li|1;	buildTree(L,mid,li);	buildTree(mid+1,R,ri);	up(id);}void fan(int id){	if(T[id].L==T[id].R)return ;	int li=id<<1,ri=li|1;	T[id].flag=0;//传递给两个子区间后该区间上不取反	T[li].flag^=1;T[ri].flag^=1;	T[li].Mw*=-1;T[li].mw*=-1;	T[ri].Mw*=-1;T[ri].mw*=-1;	swap(T[li].Mw,T[li].mw);	swap(T[ri].Mw,T[ri].mw);}void Negate(int L,int R,int id)//取反操作{	if(T[id].L==L&&T[id].R==R)	{		T[id].Mw*=-1;		T[id].mw*=-1;		swap(T[id].Mw,T[id].mw);		T[id].flag^=1;		return ;	}	int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li|1;	if(T[id].flag)	{		fan(id);	}	if(R<=mid)Negate(L,R,li);	else if(L>mid)Negate(L,R,ri);	else 	{		Negate(L,mid,li);		Negate(mid+1,R,ri);	}	up(id);}void insert(int x,int id,int w)//更新x的值{	if(T[id].L==x&&T[id].R==x)	{		T[id].Mw=T[id].mw=w;		T[id].flag=0;		return ;	}		int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li|1;	if(T[id].flag)		fan(id);	if(x<=mid)insert(x,li,w);	else insert(x,ri,w);	up(id);}int find(int L,int R,int id)//找最大值{	if(T[id].L==L&&T[id].R==R)	{		return T[id].Mw;	}	int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li|1;	if(T[id].flag)		fan(id);	if(R<=mid)return find(L,R,li);	else if(L>mid)return find(L,R,ri);	else return max(find(L,mid,li),find(mid+1,R,ri));	up(id);}int lca(int x,int y)//x到y路径上的最大值{	int ans=-inf;	while(top[x]!=top[y])	{		if(dep[top[x]]
       
        dep[y])swap(x,y);	if(x!=y)		ans=max(ans,find(ti[x]+1,ti[y],1));	return ans;}void LCA(int x,int y)//x到y路径权值取反{	while(top[x]!=top[y])	{		if(dep[top[x]]
        
         dep[y])swap(x,y);	if(x!=y)		Negate(ti[x]+1,ti[y],1);//ti[x]是x与父节点的边}int main(){	int i,n,t,x,y,w;	char str[10];	scanf("%d",&t);	while(t--)	{		memset(head,-1,sizeof(head));		num=0;		scanf("%d",&n);		for(i=1;i
         
          dep[e[x].ed])//每条边的取值在度数大的点上 swap(e[x].st,e[x].ed); insert(ti[e[x].ed],1,y); } else if(str[0]=='N') LCA(x,y); else printf("%d\n",lca(x,y)); } } return 0;}