题解2

思路

暴力做法：枚举区间求LCA。

优化：考虑快速计算合并LCA相同的区间。

枚举右端点 $r$ ，维护所有左端点 $i$ 对应的 $[i,r]$ 区间LCA，显然所有以 $r$ 为右端点的区间的LCA在根节点到 $r$ 的链上，且 $i$ 越小，LCA越浅。

使用单调栈按深度递增维护对应所有左端点的LCA，合并所有LCA相同的左端点，所有贡献即可维护。

复杂度

$O(nlogn)$

代码

略

LCA的贡献 题解

题目大意

$n$ 个节点的树（1 为根），节点 $i$ 有权值 $x_i$。数组 $a$ 是 $1\sim n$ 的排列。对每个区间 $[l,r]$，若 $a_l,\dots,a_r$ 这些节点的 LCA 是 $k$，则该区间贡献 $x_k$。求所有区间贡献之和。

算法思路

转化为：对每个节点 $k$，统计"LCA 恰好为 $k$"的区间个数，再乘 $x_k$ 求和。

用DSU on tree处理。对每个节点，维护其子树内节点在数组 $a$ 中出现的所有位置形成的若干连续段：

• 设 $S_x$ 为 $x$ 子树内节点在 $a$ 中的位置集合。区间 $[l,r]$ 的 LCA 为 $x$，当且仅当 $[l,r]$ 内的位置都属于 $S_x$，且不全部落在 $x$ 的某一个儿子的 $S$ 内。
• 因为只关心每一个连续段的左右端点，直接维护$n$个线段的左右端点，每加入一个位置，若它与左右已有的连续段相接则合并，并用 $\frac{(len)(len+1)}2$ 的增量更新"LCA 恰好为 $x$"的区间数。

先对重儿子保留结果，轻儿子暴力加/删，整体复杂度 $O(n\log n)$。

复杂度

$O(n\log n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 200010;
int n;
vector<int> g[MAXN];
int pos[MAXN];              // pos[node] = node 在数组 a 中的位置
ll w[MAXN];
int sz[MAXN], heavy[MAXN];

int segL[MAXN], segR[MAXN], mark[MAXN];
int ver[MAXN], curVer = 0;
ll cnt[MAXN];
ll total = 0;

ll tri(ll x) { return x * (x + 1) / 2; }

void addPos(int p, int u) {
    mark[p] = curVer;
    segL[p] = segR[p] = p;
    if (mark[p + 1] != curVer) segL[p + 1] = segR[p + 1] = 0;
    if (mark[p - 1] != curVer) segL[p - 1] = segR[p - 1] = 0;
    ll a = 0, b = 0;
    if (segL[p - 1] && segR[p + 1]) {
        a = p - segL[p - 1];
        b = segR[p + 1] - p;
        segR[segL[p - 1]] = segR[p + 1];
        segL[segR[p + 1]] = segL[p - 1];
    } else if (segL[p - 1]) {
        a = p - segL[p - 1];
        segR[segL[p - 1]] = p;
        segL[p] = segL[p - 1];
    } else if (segR[p + 1]) {
        b = segR[p + 1] - p;
        segL[segR[p + 1]] = p;
        segR[p] = segR[p + 1];
    }
    cnt[u] = cnt[u] - tri(a) - tri(b) + tri(a + b + 1);
}

void dfsSize(int u) {
    sz[u] = 1;
    for (int v : g[u]) {
        dfsSize(v);
        sz[u] += sz[v];
        if (sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}

void dfsAdd(int u, int target) {
    addPos(pos[u], target);
    for (int v : g[u]) dfsAdd(v, target);
}

void dfsClear(int u) {
    mark[pos[u]] = 0;
    segL[pos[u]] = segR[pos[u]] = 0;
    for (int v : g[u]) dfsClear(v);
}

void dfsDsu(int u) {
    ver[pos[u]] = ++curVer;
    for (int v : g[u]) {
        if (v == heavy[u]) continue;
        dfsDsu(v);
        dfsClear(v);
    }
    if (heavy[u]) {
        dfsDsu(heavy[u]);
        cnt[u] = cnt[heavy[u]];
        curVer = ver[pos[u]] = ver[pos[heavy[u]]];
        for (int v : g[u]) {
            if (v != heavy[u]) dfsAdd(v, u);
        }
    }
    curVer = ver[pos[u]];
    addPos(pos[u], u);
}

void dfsAnswer(int u) {
    ll k = cnt[u];
    for (int v : g[u]) {
        k -= cnt[v];
        dfsAnswer(v);
    }
    total += k * w[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        pos[x] = i;
    }
    for (int i = 1; i <= n; ++i) cin >> w[i];

    dfsSize(1);
    dfsDsu(1);
    dfsAnswer(1);
    cout << total << '\n';
    return 0;
}