问题描述

给定一棵拥有 $n$ 个结点的权值树，需处理 $q$ 次操作：

1. 路径及邻域修改：给定 $u, v, k$，将路径 $(u, v)$ 上的所有点，以及与该路径至少有一个公共点的所有邻接点的权值均改为 $k$。
2. 特定序列最大子段和查询：沿路径从 $u$ 走到 $v$，每经过一个点 $w$，依次将 $w$ 的权值和 $w$ 的所有不在路径上的邻接点（按编号升序）的权值加入序列 $S$。求 $S$ 的最大可空子段和。

$n, q \le 10^5$。

算法分析

本题的核心在于维护一种特殊的树上结构——"毛毛虫"（Caterpillar）。一个毛毛虫由一条主链（虫身）及其所有邻接点（虫足）组成。常规的重链剖分（HLD）可以高效处理路径信息，但无法直接维护邻接点的有序序列。

毛毛虫剖分的重标号策略

为了处理查询要求的特定顺序，我们需要设计特殊的 DFS 序标号方法。核心思想是让路径上的点及其轻儿子在标号上具有某种连续性。

我们采用两种不同的标号方式来应对路径合并时的方向问题：

• 正向标号 (Type 0)：在遍历重链时，先对当前节点标号，随后按升序遍历其所有轻儿子并标号，最后递归重儿子。这种方式适合处理从上到下的路径段。
• 反向标号 (Type 1)：在遍历重链时，先按降序遍历当前节点的轻儿子并标号，随后对当前节点标号，最后递归重儿子。这种方式方便在路径反转时维护正确的顺序。

线段树维护

利用上述标号，毛毛虫的修改和查询可以转化为线段树上的区间操作。线段树每个节点维护四个值：

• totalSum: 区间总和
• prefixMax: 最大前缀和
• suffixMax: 最大后缀和
• maxSubSum: 整个区间的最大子段和

合并两个区间 $[L, M]$ 和 $[M+1, R]$ 时，逻辑如下：

Node merge(Node left, Node right) {
    Node res;
    res.totalSum = left.totalSum + right.totalSum;
    res.prefixMax = max(left.prefixMax, left.totalSum + right.prefixMax);
    res.suffixMax = max(right.suffixMax, right.totalSum + left.suffixMax);
    res.maxSubSum = max({left.maxSubSum, right.maxSubSum, left.suffixMax + right.prefixMax});
    return res;
}

实现细节

在进行路径修改时，除了路径本身的重链区间，还需要注意处理每个重链顶端的父亲节点以及重链底端节点的重儿子，以覆盖整个毛毛虫区域。查询时，将路径分为从 $u$ 到 $LCA$ 和从 $LCA$ 到 $v$ 两段，分别利用两种标号下的序列进行合并。注意在 $LCA$ 处需特殊处理其父亲和儿子的贡献顺序。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct RangeInfo {
    ll sum, lmx, rmx, amx;
    static RangeInfo leaf(ll v) {
        ll val = max(0LL, v);
        return {v, val, val, val};
    }
    RangeInfo reverse() const { return {sum, rmx, lmx, amx}; }
};

RangeInfo operator+(const RangeInfo& a, const RangeInfo& b) {
    return {
        a.sum + b.sum,
        max(a.lmx, a.sum + b.lmx),
        max(b.rmx, b.sum + a.rmx),
        max({a.amx, b.amx, a.rmx + b.lmx})
    };
}

int n, q;
int weight[MAXN], parent[MAXN], depth[MAXN], sz[MAXN], hson[MAXN], top[MAXN];
vector<int> G[MAXN];
int dfn[MAXN][2], timer[2], mapping[MAXN][2], chain_end[MAXN][2], light_start[MAXN][2], light_end[MAXN][2], hson_pos[MAXN][2];

struct SegmentTree {
    RangeInfo tree[MAXN * 4];
    int lazy[MAXN * 4];
    int type;

    void push_up(int u) { tree[u] = tree[u << 1] + tree[u << 1 | 1]; }

    void apply(int u, int l, int r, int v) {
        lazy[u] = v;
        ll s = (ll)(r - l + 1) * v;
        tree[u] = {s, max(0LL, s), max(0LL, s), max(0LL, s)};
    }

    void push_down(int u, int l, int r) {
        if (lazy[u] != INF) {
            int mid = (l + r) >> 1;
            apply(u << 1, l, mid, lazy[u]);
            apply(u << 1 | 1, mid + 1, r, lazy[u]);
            lazy[u] = INF;
        }
    }

    void build(int u, int l, int r) {
        lazy[u] = INF;
        if (l == r) {
            tree[u] = RangeInfo::leaf(weight[mapping[l][type]]);
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    void update(int u, int l, int r, int ql, int qr, int v) {
        if (ql > qr) return;
        if (ql <= l && r <= qr) {
            apply(u, l, r, v);
            return;
        }
        push_down(u, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(u << 1, l, mid, ql, qr, v);
        if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr, v);
        push_up(u);
    }

    RangeInfo query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[u];
        push_down(u, l, r);
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(u << 1, l, mid, ql, qr);
        if (ql > mid) return query(u << 1 | 1, mid + 1, r, ql, qr);
        return query(u << 1, l, mid, ql, qr) + query(u << 1 | 1, mid + 1, r, ql, qr);
    }
} st[2];

void dfs1(int u, int p, int d) {
    parent[u] = p, depth[u] = d, sz[u] = 1, hson[u] = 0;
    for (int v : G[u]) {
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[hson[u]]) hson[u] = v;
    }
}

void dfs2_assign(int u, int tp) {
    top[u] = tp;
    if (u == tp) {
        auto process = [&](int cur_u, int mode) {
            light_start[cur_u][mode] = timer[mode] + 1;
            if (mode == 0) dfn[cur_u][0] = ++timer[0];
            for (int i = 0; i < (int)G[cur_u].size(); ++i) {
                int v = (mode == 0 ? G[cur_u][i] : G[cur_u][G[cur_u].size() - 1 - i]);
                if (v == hson[cur_u]) hson_pos[cur_u][mode] = timer[mode];
                else dfn[v][mode] = ++timer[mode];
            }
            if (mode == 1) dfn[cur_u][1] = ++timer[1];
            light_end[cur_u][mode] = timer[mode];
            if (hson[cur_u]) {
                int next_u = hson[cur_u];
                while(next_u) {
                    light_start[next_u][mode] = timer[mode] + 1;
                    if (mode == 0) dfn[next_u][0] = ++timer[0];
                    for (int j = 0; j < (int)G[next_u].size(); ++j) {
                        int v = (mode == 0 ? G[next_u][j] : G[next_u][G[next_u].size() - 1 - j]);
                        if (v == hson[next_u]) hson_pos[next_u][mode] = timer[mode];
                        else dfn[v][mode] = ++timer[mode];
                    }
                    if (mode == 1) dfn[next_u][1] = ++timer[1];
                    light_end[next_u][mode] = timer[mode];
                    chain_end[next_u][mode] = timer[mode];
                    next_u = hson[next_u];
                }
            }
            chain_end[cur_u][mode] = timer[mode];
        };
        process(u, 0); process(u, 1);
    }
    if (hson[u]) dfs2_assign(hson[u], tp);
    for (int v : G[u]) if (v != hson[u]) dfs2_assign(v, v);
}

int get_lca(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) v = parent[top[v]];
        else u = parent[top[u]];
    }
    return depth[u] < depth[v] ? u : v;
}

void modify(int u, int v, int k) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        st[0].update(1, 1, n, light_start[top[u]][0], chain_end[u][0], k);
        if (hson[u]) st[0].update(1, 1, n, dfn[hson[u]][0], dfn[hson[u]][0], k);
        st[1].update(1, 1, n, light_start[top[u]][1], chain_end[u][1], k);
        if (hson[u]) st[1].update(1, 1, n, dfn[hson[u]][1], dfn[hson[u]][1], k);
        u = parent[top[u]];
        st[0].update(1, 1, n, dfn[u][0], dfn[u][0], k);
        st[1].update(1, 1, n, dfn[u][1], dfn[u][1], k);
    }
    if (depth[u] < depth[v]) swap(u, v);
    st[0].update(1, 1, n, light_start[v][0], chain_end[u][0], k);
    if (hson[u]) st[0].update(1, 1, n, dfn[hson[u]][0], dfn[hson[u]][0], k);
    st[1].update(1, 1, n, light_start[v][1], chain_end[u][1], k);
    if (hson[u]) st[1].update(1, 1, n, dfn[hson[u]][1], dfn[hson[u]][1], k);
    if (parent[v]) {
        st[0].update(1, 1, n, dfn[parent[v]][0], dfn[parent[v]][0], k);
        st[1].update(1, 1, n, dfn[parent[v]][1], dfn[parent[v]][1], k);
    }
}

RangeInfo get_caterpillar_node(int u, int p, int t) {
    int start = light_start[u][t], end = light_end[u][t];
    int p_pos = dfn[p][t], h_pos = hson_pos[u][t];
    RangeInfo res = {0, 0, 0, 0};
    if (p_pos < h_pos) {
        res = st[t].query(1, 1, n, h_pos + 1, end);
        if (hson[u]) res = res + st[t].query(1, 1, n, dfn[hson[u]][t], dfn[hson[u]][t]);
        res = res + st[t].query(1, 1, n, max(p_pos + 1, start), h_pos);
        res = res + st[t].query(1, 1, n, start, p_pos - 1);
    } else {
        res = st[t].query(1, 1, n, max(p_pos + 1, start), end);
        res = res + st[t].query(1, 1, n, max(h_pos + 1, start), p_pos - 1);
        if (hson[u]) res = res + st[t].query(1, 1, n, dfn[hson[u]][t], dfn[hson[u]][t]);
        res = res + st[t].query(1, 1, n, start, min(h_pos, p_pos - 1));
    }
    return res;
}

pair<RangeInfo, int> climb(int u, int target, int t) {
    RangeInfo res = {0, 0, 0, 0};
    int last = 0;
    while (top[u] != top[target]) {
        if (u != top[u]) {
            res = res + get_caterpillar_node(u, last, t);
            res = res + st[t].query(1, 1, n, chain_end[top[u]][t] + 1, light_start[u][t] - 1);
            u = top[u];
        }
        if (t == 0) {
            res = res + get_caterpillar_node(u, last, 0);
            res = res + st[0].query(1, 1, n, dfn[u][0], dfn[u][0]);
        } else {
            res = res + st[1].query(1, 1, n, dfn[u][1], dfn[u][1]);
            res = res + get_caterpillar_node(u, last, 1);
        }
        last = u; u = parent[u];
    }
    if (u != target) {
        res = res + get_caterpillar_node(u, last, t);
        res = res + st[t].query(1, 1, n, light_start[hson[target]][t], light_start[u][t] - 1);
        last = hson[target];
    }
    return {res, last};
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int dummy; cin >> dummy >> n;
    for (int i = 1; i <= n; ++i) cin >> weight[i];
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        G[p].push_back(i);
    }
    dfs1(1, 0, 1);
    dfs2_assign(1, 1);
    for (int i = 1; i <= n; ++i) {
        mapping[dfn[i][0]][0] = i;
        mapping[dfn[i][1]][1] = i;
    }
    st[0].type = 0; st[0].build(1, 1, n);
    st[1].type = 1; st[1].build(1, 1, n);

    cin >> q;
    while (q--) {
        int op, u, v; cin >> op >> u >> v;
        if (op == 0) {
            int k; cin >> k;
            modify(u, v, k);
        } else {
            int lca = get_lca(u, v);
            auto res_u = climb(u, lca, 1);
            auto res_v = climb(v, lca, 0);
            RangeInfo ans = res_u.first.reverse();
            ans = ans + st[0].query(1, 1, n, dfn[lca][0], dfn[lca][0]);
            if (parent[lca]) ans = ans + st[0].query(1, 1, n, dfn[parent[lca]][0], dfn[parent[lca]][0]);
            
            vector<pair<int, int>> events;
            if (res_u.second && res_u.second != hson[lca]) events.push_back({dfn[res_u.second][0], 0});
            if (res_v.second && res_v.second != hson[lca]) events.push_back({dfn[res_v.second][0], 0});
            if (res_u.second != hson[lca] && res_v.second != hson[lca]) events.push_back({hson_pos[lca][0], 2});
            events.push_back({light_end[lca][0], 1});
            sort(events.begin(), events.end());
            
            int cur = light_start[lca][0] + (lca != top[lca]);
            for (auto& ev : events) {
                ans = ans + st[0].query(1, 1, n, cur, ev.first - (ev.second == 0));
                if (ev.second == 2) ans = ans + st[0].query(1, 1, n, dfn[hson[lca]][0], dfn[hson[lca]][0]);
                cur = ev.first + 1;
            }
            ans = ans + res_v.first;
            cout << ans.amx << "\n";
        }
    }
    return 0;
}