【BZOJ4127】Abs

　　2 u v 表示询问路径 (u,v) 上点权绝对值的和

接下来m行,每行一个操作,输入格式见题目描述

对于每个询问输出答案

2 3 4

9

对于100%的数据，n,m <= 10^5 且 0<= d,|a_i|<= 10^8

树链剖分

我们可以在线段树里存当前的size，负数的个数，负数最大值，绝对值总和。

若添加后负数最大值仍为负，就可用懒标记，负数个数，正数个数完成操作。

加成正数也可暂时不管（反正也不用求ans），添加时随便加

询问时若当前节点负数最大值大于0了，就暴力更新所有到由负权变正的叶节点到当前点的链

权值由负变正最多n次，所以时间复杂度仍为nlogn。

#include<bits/stdc++.h>
#define LL long long
#define O4 inline
#define inf 0x7fffffff
using namespace std;
const int N=1000005;
int n,m,a,b,c,d,e,limit;
O4 int read()
{
	char t;int u=0,k=1;t=getchar();
	while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
	while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
	return u*k;
}
int fa[N],deep[N],siz[N],son[N],top[N],num[N],flect[N],cnt=0,ed[N];
int nega[N*4],all[N*4],load[N],val[N*4];
LL tag[N*4],ans[N*4],maxx[N*4];
vector <int> Map[N];
O4 void link(int a,int b)
{
	Map[a].push_back(b);
	Map[b].push_back(a);
}
void DFS_1(int now,int las,int D)
{
	deep[now]=D;fa[now]=las;siz[now]=1;
	for(int i=0;i<Map[now].size();i++)
	{
		int tp=Map[now][i];if(tp==las)continue;
		DFS_1(tp,now,D+1);siz[now]+=siz[tp];
		if(siz[tp]>siz[son[now]])son[now]=tp;
	}
}
void DFS_2(int now,int head)
{
	top[now]=head;num[now]=++cnt;flect[cnt]=now;
	if(son[now])DFS_2(son[now],head);
	for(int i=0;i<Map[now].size();i++)
	{
		int tp=Map[now][i];
		if(tp==fa[now]||tp==son[now])continue;
		DFS_2(tp,tp);
	}ed[now]=cnt;
}
O4 void Dtag(int now,int v)
{
	ans[now]+=v*(LL)(all[now]-nega[now]*2);
	maxx[now]+=v;val[now]+=v;
	tag[now]+=v;
}
O4 void down(int now)
{
	if(tag[now])
	{
		Dtag(now*2,tag[now]);
		Dtag(now*2+1,tag[now]);
		tag[now]=0;
	}
}
O4 void up(int now)
{
	int L=now*2,R=now*2+1;
	ans[now]=ans[L]+ans[R];
	nega[now]=nega[L]+nega[R];
	if(nega[now]==0)maxx[now]=-inf;
	else maxx[now]=max(maxx[L],maxx[R]);
}
O4 void change(int now,int L,int R,int ql,int qr,int val)
{
	if(L>qr||R<ql)return;
	if(ql<=L&&R<=qr){Dtag(now,val);return;}
	int mid=(L+R)>>1;down(now);
	change(now*2,L,mid,ql,qr,val);
	change(now*2+1,mid+1,R,ql,qr,val);up(now);
}
O4 void build(int now,int L,int R)
{
	all[now]=R-L+1;
	if(L==R)
	{
		val[now]=load[flect[L]];
		maxx[now]=min(val[now],0);
		nega[now]=(val[now]<0);
		ans[now]=abs(val[now]);
		return;
	}
	int mid=(L+R)>>1;
	build(now*2,L,mid);build(now*2+1,mid+1,R);up(now);
}
O4 void deal(int now,int L,int R)
{
	if(L==R)
	{
		nega[now]=0;
		ans[now]=val[now];
		maxx[now]=-inf;
		return;
	}
	int mid=(L+R)>>1;down(now);
	if(maxx[now*2]>0)deal(now*2,L,mid);
	if(maxx[now*2+1]>0)deal(now*2+1,mid+1,R);up(now);
}
O4 LL ask(int now,int L,int R,int ql,int qr)
{
	if(L>qr||R<ql)return 0;
	if(maxx[now]>0)deal(now,L,R);
	if(ql<=L&&R<=qr)return ans[now];
	int mid=(L+R)/2;down(now);
	LL tp=ask(now*2,L,mid,ql,qr)+ask(now*2+1,mid+1,R,ql,qr);
	up(now);return tp;
}
O4 LL LCA(int a,int b,int c,int d)
{
	int q1=top[a],q2=top[b];
	LL tp=0;
	while(q1!=q2)
	{
		if(deep[q1]<deep[q2])swap(q1,q2),swap(a,b);
		if(c==233)change(1,1,n,num[q1],num[a],d);
		else tp+=ask(1,1,n,num[q1],num[a]);
		a=fa[q1];q1=top[a];
	}
	if(deep[a]>deep[b])swap(a,b);
	if(c==233)change(1,1,n,num[a],num[b],d);
	else return tp+ask(1,1,n,num[a],num[b]);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)load[i]=read();
	for(int i=1;i<n;i++)
	{
		a=read();b=read();
		Map[a].push_back(b);
		Map[b].push_back(a);
	}
	DFS_1(1,0,1);DFS_2(1,1);build(1,1,n);
	while(m--)
	{
		a=read();b=read();c=read();
		if(a==1)LCA(b,c,233,read());
		else printf("%lld\n",LCA(b,c,0,0));
	}
	return 0;
}