T6

虚树

题目大意

现在有一颗树，树上有一些节点，我们可以待在某个节点一段时间$t_i$，最终赚得一定的钱数$p_i$，同时在一条边上移动会花费1个单位时间，求在一个定时间 $w_i$ 最多会赚多少钱。

题解思路

问题一

当树的节点比较小的时候，我们可以通过什么方法来解决这个问题。
很明显我们可以通过一个背包来解决这个问题。
在树上我们根据花费多少模拟背包操作，之后将背包中的信息整合，对父节点进行背包操作。
但是节点数似乎很多，直接背包容易tle，

优化

现在树上一共有 $n$ 个点,在这 $n$ 个节点上进行背包 $dp$ ,维护会发生超时，那么我们可以怎么做呢？首先，我们发现可以赚钱的节点很少 $m$，我们沿着这些节点往上走，我们发现，最多会有 $m$ 次相遇，也就意味着，不同的背包最多合并 $m$ 次。那么我们是否只要在这些需要合并的点上进行记录就可以了？
我们叫这些合并的点叫做虚点。
这些虚点我们可以通过 $lca$ 求得。

关于求 $lca$ 可以实现树剖或者倍增预处理并实现，之后在新树上进行dp

复杂度分析

O($n + m\log n + m\times W^2$)

参考代码

 #include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define int ll

//点 工作 总时间
const int maxn = 5e5+10;
int n, m, w;
vector<int> mp[maxn];
unordered_map<int, int> tim;
unordered_map<int, int> we;
int fa[maxn], top[maxn], son[maxn], dfn[maxn], dep[maxn], siz[maxn];
int tot = 1;
vector<array<int, 3> > v;
set<int> mp2[maxn];

void dfs1(int now) {
    siz[now] = 1;
    for (auto c: mp[now]) {
        dep[c] = dep[now] + 1;
        dfs1(c);
        siz[now] += siz[c];

        if (siz[c] > son[siz[now]]) {
            son[now] = c;
        }
    }
}

void dfs2(int now) {
    dfn[now] = tot++;
    if (son[fa[now]] == now) {
        top[now] = top[fa[now]];
    } else {
        top[now] = now;
    }
    if (son[now]) {
        dfs2(son[now]);
    }
    for (auto i: mp[now]) {
        if (i == son[now])continue;
        dfs2(i);
    }
}

int lca(int p,int q) {
    while (top[q] != top[p]) {
        //            cerr<<dep[top[q]]<<" "<<dep[top[p]]<<endl;
        if (dep[top[q]] < dep[top[p]])
            swap(q, p);
        q = fa[top[q]];
    }
    if (dep[q] < dep[p])swap(q, p);
    return p;
}

int cost(int u,int v) {
    return 2 * abs(dep[u] - dep[v]);
}

void build_virtual_tree() {
    sort(v.begin(), v.end(), [&](array<int, 3> a, array<int, 3> b) {
        return dfn[a[0]] < dfn[b[0]];
    });
    vector<int> a;
    for (int i = 0; i < m; ++i) {
        a.emplace_back(v[i][0]);
        a.emplace_back(lca(v[i][0], v[i + 1][0]));
    }
    a.emplace_back(v[m][0]);
    sort(a.begin(), a.end(), [&](int a1, int b1) {
        return dfn[a1] < dfn[b1];
    });
    int sizs = a.size();
    for (int i = 0; i < sizs - 1; i++) {
        int lc = lca(a[i], a[i + 1]);
        if (lc == a[i + 1])continue;
        mp2[lc].emplace(a[i + 1]);
        mp2[a[i + 1]].emplace(lc);
    }
}

vector<int> dp(int f, int t) {
    vector<int> fas(w + 10);
    fas[tim[t]] = we[t];
    for (auto c: mp2[t]) {
        if (c == f)continue;
        vector<int> v1 = dp(t, c);
        int mul = cost(t, c);
        for (int i = max(w - 2 * dep[t], 0ll); i >= 0; i--) {
            for (int j = 0; j <= w; j++) {
                if (i - mul - j < 0)break;
                fas[i] = max(fas[i], v1[j] + fas[i - mul - j]);
            }
        }
    }
    return fas;
}

void solve() {
    //7 3 10
    cin >> n >> m >> w;

    v.resize(m + 1);

    v[0] = {1, 0, 0};


    siz[0] = 0;
    dep[0] = 0;
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        mp[f].emplace_back(i);
        fa[i] = f;
    }
    for (int i = 1; i <= m; i++) {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
        tim[v[i][0]] = v[i][1];
        we[v[i][0]] = v[i][2];
    }

    dfs1(1);
    dfs2(1);
    build_virtual_tree();
    vector<int> aa = dp(0, 1);
    int maxs = -1;
    for (int i = 0; i <= w; i++) {
        maxs = max(maxs, aa[i]);
    }
    cout << maxs << endl;
}


signed main() {
    IOS
    int t = 1;
    //    cin >> t;
    while (t--)solve();
}

本题可以在分组背包中进行一定的剪枝通过，如过深的节点忽略，将原理数组背包转换为离散化背包，可以大量优化计算的过程，