题面
Sample Input
5 7
2 -1 -3 1 1
1 2
1 3
3 4
3 5
2
1 3 0
2
1 2 1
2
1 1 -3
2
Sample Output
2
4
5
2
HINT
Solution
首先考虑序列上的这个问题: 给定一个序列, 有两种操作
- 修改一个位置上的值
- 询问某个区间中的连续段的最大权值和
做法是: 用一个线段树维护这个序列, 每个节点所对应的区间记录以下4个信息:
-
sum表示整个区间的权值和 -
leftMax表示以包含从最左边开始的区间的连续段最大权值和 -
rightMax与上面相反 -
max表示整个区间中连续段最大权值和
则我们可以通过上述信息合并两个区间的信息.
考虑如何转化到树上解决: 我们首先进行树链剖分. 我们用sum[u]记录\(u\)这个点的权值加上以\(u\)的每个字节点为根的连通块的最大权值和. 我们用类似于序列上的方法维护\(sum\)即可. 修改一个点的权值时, 往上跳修改即可.
实现的时候把线段树上的信息合并重载为运算符会比较简洁.
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1; char c;
while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
const int N = (int)1e5;
int n;
multiset<int> ans;
struct data
{
int leftMax, rightMax, mx, sum;
inline data() { leftMax = rightMax = mx = sum = 0; }
inline data friend operator +(const data &a, const data &b)
{
data res;
res.sum = a.sum + b.sum;
res.leftMax = max(a.leftMax, a.sum + b.leftMax);
res.rightMax = max(b.rightMax, b.sum + a.rightMax);
res.mx = max(res.leftMax, res.rightMax);
res.mx = max(res.mx, a.mx); res.mx = max(res.mx, b.mx);
res.mx = max(res.mx, a.rightMax + b.leftMax);
return res;
}
};
struct segmentTree
{
data nd[N << 2];
void modify(int u, int L, int R, int pos, int x)
{
if (L == R)
{
nd[u].leftMax = nd[u].rightMax = nd[u].mx = max(0, x);
nd[u].sum = x;
return;
}
if (pos <= L + R >> 1) modify(u << 1, L, L + R >> 1, pos, x);
else modify(u << 1 | 1, (L + R >> 1) + 1, R, pos, x);
nd[u] = nd[u << 1] + nd[u << 1 | 1];
}
inline void modify(int pos, int x) { modify(1, 1, n, pos, x); }
data query(int u, int curL, int curR, int L, int R)
{
if (curL >= L && curR <= R) return nd[u];
int mid = curL + curR >> 1;
data res;
if (L <= mid) res = res + query(u << 1, curL, mid, L, R);
if (R > mid) res = res + query(u << 1 | 1, mid + 1, curR, L, R);
return res;
}
inline data query(int L, int R) { return query(1, 1, n, L, R); }
}seg;
struct tree
{
struct node
{
int w;
vector<int> edg; int pre;
int sz, hvy;
int tp, id, lst;
int sum;
inline node() { edg.clear(); }
}nd[N + 1];
inline void addEdge(int u, int v) { nd[u].edg.push_back(v); nd[v].edg.push_back(u); }
void getSize(int u, int pre)
{
nd[u].pre = pre; nd[u].hvy = -1; nd[u].sz = 1;
for (auto v : nd[u].edg) if (v != pre)
{
getSize(v, u); nd[u].sz += nd[v].sz;
if (nd[u].hvy == -1 || nd[v].sz > nd[nd[u].hvy].sz) nd[u].hvy = v;
}
}
int clk;
int work(int u, int tp)
{
nd[u].tp = tp; nd[u].id = ++ clk;
if (~ nd[u].hvy) work(nd[u].hvy, tp);
else
{
for (int v = u; v != nd[u].tp; v = nd[v].pre) nd[v].lst = nd[u].id;
nd[nd[u].tp].lst = nd[u].id;
}
nd[u].sum = nd[u].w;
for (auto v : nd[u].edg) if (v != nd[u].pre && v != nd[u].hvy) nd[u].sum += work(v, v);
seg.modify(nd[u].id, nd[u].sum);
if (u == tp)
{
data res = seg.query(nd[u].id, nd[u].lst);
ans.insert(res.mx);
return res.leftMax;
}
return 0;
}
inline void decomposition() { getSize(1, -1); clk = 0; work(1, 1); }
inline void modify(int u, int x)
{
int tmp = nd[u].w; nd[u].w = x;
for (; ~ u; u = nd[nd[u].tp].pre)
{
nd[u].sum = nd[u].sum - tmp + x;
data res = seg.query(nd[nd[u].tp].id, nd[nd[u].tp].lst);
tmp = res.leftMax;
ans.erase(ans.find(res.mx));
seg.modify(nd[u].id, nd[u].sum);
res = seg.query(nd[nd[u].tp].id, nd[nd[u].tp].lst);
x = res.leftMax;
ans.insert(res.mx);
}
}
}T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("sub.in", "r", stdin);
freopen("sub.out", "w", stdout);
#endif
using namespace Zeonfai;
n = getInt(); int m = getInt();
for (int i = 1; i <= n; ++ i) T.nd[i].w = getInt();
for (int i = 1, u, v; i < n; ++ i) u = getInt(), v = getInt(), T.addEdge(u, v);
ans.clear();
T.decomposition();
for (int i = 0; i < m; ++ i)
{
int opt = getInt();
if (opt == 1)
{
int u = getInt(), x = getInt();
T.modify(u, x);
}
else
{
multiset<int>::iterator p = ans.end();
printf("%d\n", *(-- p));
}
}
}