Description:

给定一棵树，有 $N$ 个节点，每一个节点都有一个权值 $x_i$ ， $Q$ 次操作： $1$ $a$ $b$ 查询 $(a,b)$ 这条链上的最大子段和 $2$ $a$ $b$ $c$ 将 $(a,b)$ 这条链上的所有点权变为 $c$

$1\le N,Q\le 100000$

Solution:

$LCT$ 维护树，需要注意覆盖标记初值赋成 $-INF$ ， $LCT$ 打 $rev$ 标记时交换 $lsum$ 和 $rsum$ ，注意 $pushdown$ 位置。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define INF 0x3f3f3f3f

struct node

{

	int fa,c[2],v,ls,rs,ms,s,tag,siz;

	bool rev;

	node(){fa = c[0] = c[1] = ls = rs = ms = s = siz = 0;rev = false;tag = -INF;}

}t[MAXN];

void maintain(int rt)

{

	int lc = t[rt].c[0],rc = t[rt].c[1];

	t[rt].siz = t[lc].siz + t[rc].siz + 1;

	t[rt].s = t[lc].s + t[rt].v + t[rc].s;

	t[rt].ls = max(t[lc].ls,t[lc].s + t[rt].v + t[rc].ls);

	t[rt].rs = max(t[rc].rs,t[rc].s + t[rt].v + t[lc].rs);

	t[rt].ms = max(max(t[lc].ms,t[rc].ms),t[lc].rs + t[rt].v + t[rc].ls);

	return;

}

void pushdown(int rt)

{

	if(t[rt].rev)

	{ 

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[t[rt].c[0]].ls,t[t[rt].c[0]].rs);

		swap(t[t[rt].c[1]].ls,t[t[rt].c[1]].rs);

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	if(t[rt].tag != -INF)

	{

		for(int i = 0;i <= 1;++i)

		{

			int ch = t[rt].c[i],k = max(t[rt].tag,0);

			t[ch].v = t[rt].tag;

			t[ch].ms = t[ch].ls = t[ch].rs = k * t[ch].siz;

			t[ch].s = t[rt].tag * t[ch].siz;

			t[ch].tag = t[rt].tag;

		}

		t[rt].tag = -INF;

	}

	return;

}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa;

	pushdown(z);pushdown(y);

	int fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

void splay(int k)

{

	s.push(k);

	for(int i = k;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(k))

	{

		int y = t[k].fa;

		if(isroot(y)){rotate(k);return;}

		if(id(k) == id(y)){rotate(y);rotate(k);}

		else{rotate(k);rotate(k);}

	}

	return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;swap(t[k].ls,t[k].rs);return;}

void link(int x,int y){makeroot(x);t[x].fa = y;return;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&t[i].v);

		t[i].siz = 1;

	}

	int x,y;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&x,&y);

		link(x,y);

	}

	scanf("%d",&m);

	int opt,z;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d%d",&x,&y);

			makeroot(x);access(y);splay(y);

			printf("%d\n",t[y].ms);

		}

		else

		{

			scanf("%d%d%d",&x,&y,&z);

			makeroot(x);access(y);splay(y);

			t[y].tag = t[y].v = z;

			int k = max(z,0);

			t[y].ms = t[y].ls = t[y].rs = k * t[y].siz;

			t[y].s = z * t[y].siz;

		}

	}

	return 0;

}