樱桃莓莓
题目链接：YBT2023寒假Day3 C
题目大意
给你一棵有根数，点有 a,b 两种权值。
然后一个点的分数是它以及它所有祖先的 a 权值和的绝对值乘上 b 权值和的绝对值。
然后有两种操作，给一个点的 a 权值加一个正数，或者询问一个子树里面分数最大的点的分数。
思路
注意到操作只加 \(a\) 而且只会变大。
然后转化一些先预处理求出每个点及其祖先的 \(a\) 权值和以及 \(b\) 的，然后操作变成每次修改和询问一个子树。
然后对于绝对值，因为求的是最大，我们可以一个点弄两个候选，分别是 \(a,b\) 与 \(a,-b\)。（总有一个是正的）
然后你考虑这个 \((a+d)b\) 这个形式求它的最大值。
会发现其实可以看做 \(-d\) 为斜率的直线经过 \((b,ab)\) 的点，在 \(y\) 轴截距最大值。
那随着 \(d\) 增大，答案是单向移动的（经过排序之后）。
（然后有一个做法就是分块，每个大块维护凸包，每次修改散块就暴力重构）
然后也可以用线段树，对于每个位置求出答案更改需要 \(d\) 增长的量。
加的时候如果当前区间被完全覆盖而且增长的量还不至于发生改变，就直接加。
否则就递归下去做。（那这样每个地方增长的量都是定的，所以是 \(n\sqrt{n}\) 的）
代码
#include<cstdio>
#include<iostream>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 2e5 + 100;
struct node {
int to, nxt;
}e[N << 1];
int n, q, fa[N], a[N], b[N], blo[N], bl[N], br[N];
int le[N], KK, st[N], ed[N], tot;
ll asum[N], bsum[N];
pair <ll, ll> pp[N << 1];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void dfs0(int now, int suma, int sumb) {
suma += a[now]; sumb += b[now]; asum[now] = suma; bsum[now] = sumb;
pp[++tot] = make_pair(asum[now], bsum[now]); st[now] = tot; pp[++tot] = make_pair(asum[now], -bsum[now]);
for (int i = le[now]; i; i = e[i].nxt) {
dfs0(e[i].to, suma, sumb);
}
ed[now] = tot;
}
ll Abs(ll x) {return x < 0 ? -x : x;}
struct XD_tree {
ll ax[N << 3], bx[N << 3], tim[N << 3], lzy[N << 3];
void downa(int now, ll x) {
lzy[now] += x; ax[now] += x; tim[now] -= x;
}
void down(int now) {
if (lzy[now]) {
downa(now << 1, lzy[now]); downa(now << 1 | 1, lzy[now]);
lzy[now] = 0;
}
}
void up(int now) {
if (ax[now << 1] * bx[now << 1] > ax[now << 1 | 1] * bx[now << 1 | 1]) ax[now] = ax[now << 1], bx[now] = bx[now << 1];
else ax[now] = ax[now << 1 | 1], bx[now] = bx[now << 1 | 1];
tim[now] = min(tim[now << 1], tim[now << 1 | 1]);
if (bx[now << 1] != bx[now << 1 | 1]) {
ll ds = (ax[now << 1 | 1] * bx[now << 1 | 1] - ax[now << 1] * bx[now << 1]) / (bx[now << 1] - bx[now << 1 | 1]);
if (ds >= 0) tim[now] = min(tim[now], ds);
}
}
void build(int now, int l, int r) {
if (l == r) {
ax[now] = pp[l].first; bx[now] = pp[l].second;
tim[now] = INF; lzy[now] = 0; return ;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
up(now);
}
void update(int now, int l, int r, int L, int R, ll x) {
if (L <= l && r <= R && tim[now] >= x) {
downa(now, x); return ;
}
int mid = (l + r) >> 1; down(now);
if (L <= mid) update(now << 1, l, mid, L, R, x);
if (mid < R) update(now << 1 | 1, mid + 1, r, L, R, x);
up(now);
}
ll query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return ax[now] * bx[now];
int mid = (l + r) >> 1; down(now); ll re = 0;
if (L <= mid) re = max(re, query(now << 1, l, mid, L, R));
if (mid < R) re = max(re, query(now << 1 | 1, mid + 1, r, L, R));
return re;
}
}T;
int main() {
freopen("ds.in", "r", stdin);
freopen("ds.out", "w", stdout);
scanf("%d %d", &n, &q);
for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), add(fa[i], i);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
dfs0(1, 0, 0); T.build(1, 1, tot);
while (q--) {
int op; scanf("%d", &op);
if (op == 1) {
int u, x; scanf("%d %d", &u, &x);
T.update(1, 1, tot, st[u], ed[u], x);
}
if (op == 2) {
int u; scanf("%d", &u);
printf("%lld\n", T.query(1, 1, tot, st[u], ed[u]));
}
}
return 0;
}