Yuri L

· · 题解

严格线性做法，但是根本没法比 1log 快很多，唉唉。

一个观察是，如果一个特殊点的子树内还有特殊点，那么可以直接给他扔掉。那么一条链就最多被两个特殊点的子树包含了。处理出来这些特殊点子树内包含的路径长度 len，那么说明此时选这个点会有一个 w\times len 的贡献。这里瓶颈在于，求路径长度需要 LCA，不过可以用 DFN LCA 套个你喜欢的线性 RMQ \mathcal{O}(n)-\mathcal{O}(1) 做掉。

由于一次操作是对其后的路径产生影响，不妨倒序做，每次会给 \mathcal{O}(1) 个特殊点加上一个系数，并查询最优的操作。这等价于单点加全局最小值。你考虑把所有操作再逆序处理，变成单点减全局最小值，是不是就看懂了？容易做到线性。

至此就整题做到 \mathcal{O}(n+m) 了 www

:::info[Code]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 lll;

const int MAXN = 1e6 + 10;

int deg[MAXN], g[MAXN << 1], fa[MAXN], pos[MAXN];

namespace LCA { // O(n)-O(1)

    int a[MAXN], dfn[MAXN], tp;

    inline  
    void init() {
        int t = 1; pos[1] = 1;
        for (; t; ) {
            int u = pos[t--]; a[dfn[u] = ++tp] = dfn[fa[u]];
            for (int i = deg[u] + 1; i <= deg[u + 1]; i++) {
                if (g[i] == fa[u]) continue;
                fa[g[i]] = u, pos[++t] = g[i];
            }
        }
        for (int i = 1; i <= tp; i++) pos[dfn[i]] = i;
    }

    typedef unsigned long long ull;

    const int MAXM = MAXN + 63 >> 6;

    int st[14][MAXM], pre[MAXN], suf[MAXN]; ull w[MAXN];

    inline 
    void build_rmq(int n) {
        int m = n + 63 >> 6;
        for (int i = 1; i <= m; i++) st[0][i] = 1e9;
        for (int i = 1; i <= m; i++) {
            int l = i - 1 << 6 | 1, r = min(n, i << 6);
            pre[l] = a[l], suf[r] = a[r];
            for (int j = l + 1; j <= r; j++) pre[j] = min(pre[j - 1], a[j]);
            for (int j = r - 1; j >= l; j--) suf[j] = min(suf[j + 1], a[j]);
            st[0][i] = pre[r];
        }
        for (int i = 1; i <= __lg(m); i++) {
            for (int j = 1; j + (1 << i) - 1 <= m; j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
            }
        }
        static int s[64];
        for (int i = 1; i <= m; i++) {
            int l = i - 1 << 6 | 1, r = min(i << 6, n), tp = 0; ull msk = 0;
            for (int j = l; j <= r; j++) {
                for (; ~tp && a[s[tp]] >= a[j]; msk ^= 1llu << s[tp--] - l);
                w[j] = msk |= 1llu << (s[++tp] = j) - l;
            }
        }
    }

    inline 
    int lca(int l, int r) {
        if (l == r) return l; l = dfn[l], r = dfn[r];
        if (l > r) swap(l, r); int p = ++l + 63 >> 6, q = r + 63 >> 6;
        if (p == q) {
            int pl = p - 1 << 6 | 1;
            return pos[a[l + __builtin_ctzll(w[r] >> l - pl)]];
        }
        int res = min(suf[l], pre[r]);
        if (p + 1 < q) {
            int k = __lg(--q - ++p + 1);
            res = min(res, min(st[k][p], st[k][q - (1 << k) + 1]));
        }
        return pos[res];
    }
}

using LCA::lca;

int c[MAXN], d[MAXN], sz[MAXN];

int a[MAXN]; ll val[MAXN], p[MAXN];

lll botan(
        const int &n, 
        const vector<int> &SpIds, 
        const vector<pair<int, int>> &G, 
        const vector<tuple<int, int, int>> &Ops) {
    int m = 0, q = Ops.size();
    for (auto [u, v] : G) ++deg[u], ++deg[v];
    for (int i = 1; i <= n; i++) deg[i + 1] += deg[i];
    for (auto [u, v] : G) g[deg[u]--] = v, g[deg[v]--] = u;
    LCA::init(), LCA::build_rmq(n);
    for (int i : SpIds) ++sz[i];
    for (int i = n; i > 1; i--) {
        int u = pos[i]; sz[fa[u]] += sz[u];
    }
    for (int i : SpIds) if (sz[i] == 1) a[c[i] = ++m] = i;
    for (int i = 2; i <= n; i++) {
        int u = pos[i];
        if (c[fa[u]]) c[u] = c[fa[u]], d[u] = d[fa[u]] + 1;
    }
    auto add = [&](int k, int x, int i) -> void { p[i] = min(p[i], val[k]), val[k] += x; };
    for (int i = q - 1; ~i; i--) {
        if (get<0>(Ops[i]) == 2) continue; p[i] = 1e18;
        int u = get<1>(Ops[i]), v = get<2>(Ops[i]);
        if (!c[u] && !c[v]) continue;
        if (c[u] == c[v]) add(c[u], d[u] + d[v] - d[lca(u, v)] * 2 + 1, i);
        else {
            if (c[u]) add(c[u], d[u] + 1, i);
            if (c[v]) add(c[v], d[v] + 1, i);
        }
    }
    lll ans = 0; ll w = *min_element(val + 1, val + m + 1);
    for (int i = 0; i < q; i++) {
        if (get<0>(Ops[i]) == 1) w = min(w, p[i]);
        else ans += (ll)w * get<1>(Ops[i]);
    }
    return ans;
}

#ifndef ONLINE_JUDGE

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vector<int> SpIds(k);
    for (int i = 0; i < k; i++) scanf("%d", &SpIds[i]);
    vector<pair<int, int>> G(n - 1);
    for (int i = 0; i < n - 1; i++) scanf("%d%d", &G[i].first, &G[i].second);
    vector<tuple<int, int, int>> Ops;
    for (int i = 0, op, x, y; i < m; i++) {
        scanf("%d%d", &op, &x), y = 0;
        if (op == 1) scanf("%d", &y);
        Ops.emplace_back(op, x, y);
    }
    lll ans = botan(n, SpIds, G, Ops);
    printf("%lld", (ll)ans);
}

#endif

:::