P3233:[HNOI2014]世界树题解

思路

这道题对初学虚树的人来讲简直就是噩梦…之前打了一个 30 分暴力未果,遂转向题解。知道了一个叫做虚树的东西,然后抄了一下午的题解才 AC。

我先来解释一下虚树这个数据结构(?)。在一棵书上,会有关键点集和非关键点集,在一些问题中我们只需要用到关键点之间的关系,而非关键点集便不在那么重要。这个时候我们可以建立一个虚树。

建立虚树的过程相当之繁琐,我在这里不在详细讲,可以使用单调栈和 LCA 算法以极高的效率搞定。详细见:https://oi-wiki.org/ds/virtual-tree/

以下为代码:

// P3233.cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define pr pair<int, int>
using namespace std;
const int MX_N = 300020;
int head[MX_N], current;
struct edge
{
    int to, nxt;
} edges[MX_N << 1];
int fa[MX_N], stfa[20][MX_N], n, dep[MX_N], anses[MX_N], id[MX_N], dfn = 0, q, m;
int tmpx, tmpy, st[MX_N], top = 1, tsiz[MX_N];
pr mx[MX_N];
bool vis[MX_N];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void preprocess()
{
    for (int i = 1; i <= n; i++)
        stfa[0][i] = fa[i];
    for (int tim = 1; tim < 20; tim++)
        for (int u = 1; u <= n; u++)
            stfa[tim][u] = stfa[tim - 1][stfa[tim - 1][u]];
}
int jump(int u, int p)
{
    for (int i = 0; i <= 19; i++)
        if ((p >> i) & 1)
            u = stfa[i][u];
    return u;
}
int getLca(int a, int b)
{
    // b is deeper;
    if (dep[a] > dep[b])
        swap(a, b);
    b = jump(b, dep[b] - dep[a]);
    if (a == b)
        return a;
    for (int tim = 19; tim >= 0; tim--)
        if (stfa[tim][a] != stfa[tim][b])
            a = stfa[tim][a], b = stfa[tim][b];
    return fa[a];
}
void dfs_fa(int u)
{
    id[u] = ++dfn;
    tsiz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (fa[u] != edges[i].to)
            fa[edges[i].to] = u, dfs_fa(edges[i].to), tsiz[u] += tsiz[edges[i].to];
}
bool compare(const int &a, const int &b) { return id[a] < id[b]; }
void dfs_1(int u)
{
    if (vis[u])
        mx[u] = make_pair(0, u);
    else
        mx[u] = make_pair(1e8, 0);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        dfs_1(to);
        pr tmp = mx[to];
        tmp.first = dep[mx[to].second] - dep[u];
        mx[u] = min(mx[u], tmp);
    }
}
void dfs_2(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        pr p = mx[u];
        p.first += dep[edges[i].to] - dep[u];
        mx[edges[i].to] = min(mx[edges[i].to], p);
        dfs_2(edges[i].to);
    }
    anses[mx[u].second] = max(anses[mx[u].second], tsiz[u]);
}
void dfs_3(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int x = mx[u].second, y = mx[edges[i].to].second;
        if (x != y)
        {
            int dist = dep[x] + dep[y] - (dep[getLca(x, y)] << 1);
            int z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first);
            if (dist & 1)
                anses[x] -= tsiz[z];
            else
            {
                if (z != u && z != edges[i].to)
                    z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first - (x < y));
                else if (z == u)
                    z = jump(edges[i].to, (dist >> 1) - mx[edges[i].to].first - 1);
                anses[x] -= tsiz[z];
            }
            if (edges[i].to != z)
                anses[y] += tsiz[z] - tsiz[edges[i].to];
        }
        dfs_3(edges[i].to);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs_fa(1);
    preprocess();
    scanf("%d", &q);
    while (q--)
    {
        current = 0;
        scanf("%d", &m);
        vector<int> harr, arrs;
        for (int i = 1; i <= m; i++)
            scanf("%d", &tmpx), vis[tmpx] = true, harr.push_back(tmpx), anses[tmpx] = 0, arrs.push_back(tmpx);
        sort(harr.begin(), harr.end(), compare);
        // start to build the virtual tree;
        // prep for the stack;
        st[top = 1] = 1, head[1] = -1;
        for (int i = 0; i < m; i++)
        {
            if (harr[i] == 1)
                continue;
            int curtpt = harr[i], lca = getLca(curtpt, st[top]);
            if (lca != st[top])
            {
                while (id[lca] < id[st[top - 1]])
                    addpath(st[top - 1], st[top]), top--;
                if (id[lca] > id[st[top - 1]])
                    head[lca] = -1, addpath(lca, st[top]), st[top] = lca;
                else
                    addpath(lca, st[top--]);
            }
            head[curtpt] = -1, st[++top] = curtpt;
        }
        for (int i = 1; i < top; i++)
            addpath(st[i], st[i + 1]);
        dfs_1(1), dfs_2(1), dfs_3(1);
        for (int i = 0; i < m; i++)
            printf("%d ", anses[arrs[i]]);
        printf("\n");
        for (int i = 0; i < m; i++)
            vis[arrs[i]] = false;
    }
    return 0;
}

 

P2014:选课题解

思路

一开始我还以为是拓扑排序,后面写代码的时候仔细思考了这道题,应该是树形dp。

主要的思路就是做一个编号为0的虚拟节点(这个点权重(学分)为0),然后建一棵树。构造dp方程\(F[u][size] = F[son][subsize] + F[u][size – subsize]\)。其中这里需要注意的是,这个本质上是一个树形的01背包,所以在生成dp表的时候需要反着推。(坑了我一个小时,哎我还是太菜了)输出的时候因为有点0的存在所以背包容量会比之前的大一个单位。

还需要注意的是,在我的代码中,我用了一个dfss来计算每个子背包的容量,不知道有没有必要,希望大佬能指出是否有这个必要。

代码

// P2014.cpp
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 2100;
struct edge
{
    int to, next;
} edges[maxn << 1];
int deg[maxn];
int indeg[maxn];
int head[maxn];
int weight[maxn];
int current = 0;

int n, m;

void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int F[maxn][maxn];
int sizes[maxn];

void dfss(int u)
{
    sizes[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfss(edges[i].to);
        sizes[u] += sizes[edges[i].to];
    }
}

void dfs(int u)
{
    for (int i = 1; i <= m; i++)
        F[u][i] = weight[u];
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfs(edges[i].to);
        int jto = edges[i].to;
        for (int len = m + 1; len >= 2; len--)
            for (int lens = 0; lens < len; lens++)
                F[u][len] = max(F[u][len], F[u][len - lens] + F[jto][lens]);
    }
}

int main()
{
    fill(head, head + maxn, -1);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int k, s;
        cin >> k >> s;
        weight[i] = s;
        addpath(k, i), indeg[i]++, deg[k]++;
    }
    dfss(0);
    dfs(0);
    cout << F[0][m + 1];
    return 0;
}

P1352:没有上司的舞会题解

思路

这是一道非常经典的树形DP,题中直接讲到这是树形结构。建树之后,状态转移方程不难想出:

  • 对于每一个点,F[u][0]代表不选这个点的最优解,F[u][1]代表选这个点的最优解。
  • 对于运行时的每个点,都有F[u][1] = happiness[u]。
  • 对于一个点的孩子遍历,都有F[u][0] += max(F[v][1], F[v][0]),F[u][1] += F[v][0]。

由此,我们可以轻松的写出下列的代码。

代码

// P1352.cpp
#include <iostream>

using namespace std;
// Data Structure;
const int maxn = 6100;
int n;
int R[maxn];
// Graph stuff;
// Notice: the edge space should be doubled;
struct edge
{
    int to, next;
} edges[maxn << 1];
int head[maxn];
int current = 0;
int F[maxn][2];
int deg[maxn];
// DFS func;
void DFS(int curt)
{
    // Initalize the DP Table;
    F[curt][1] = R[curt];
    // Find the subnodes;
    for (int i = head[curt]; i != -1; i = edges[i].next)
    {
        // Call the subtree to be ready;
        DFS(edges[i].to);
        // Deciding;
        F[curt][1] += F[edges[i].to][0];
        F[curt][0] += max(F[edges[i].to][0], F[edges[i].to][1]);
    }
}

void add_path(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int main()
{
    // Initialize;
    cin >> n;
    fill(head, head + maxn, -1);
    for (int i = 1; i <= n; i++)
        cin >> R[i];
    int a, b;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a >> b, add_path(b, a);
        deg[a]++;
    }
    cin >> a >> b;
    // Find the root node by the degrees saved before;
    int root = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
        {
            root = i;
            break;
        }
    // Start to dp;
    DFS(root);
    // Output;
    cout << max(F[root][0], F[root][1]);
    return 0;
}

 

P1137:旅行计划题解

思路

好久没有写拓扑排序了。今天看到这题看了半天,由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的,所以我们只需一头往下走就好,用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。

代码

// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;

void add_edge(int a, int b)
{
    to[current] = b;
    next[current] = points[a];
    points[a] = current++;
}

void toposort()
{
    queue<int> waiting;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            waiting.push(i), res[tot++] = i;
    while (!waiting.empty())
    {
        int curt = waiting.front();
        waiting.pop();
        for (int edge = points[curt]; edge != -1; edge = next[edge])
        {
            indeg[to[edge]]--;
            if (indeg[to[edge]] == 0)
                waiting.push(to[edge]), res[tot++] = to[edge];
        }
    }
}

void DP()
{
    for (int i = 1; i <= n; i++)
        dp[i] = 1;
    for (int i = 0; i < n; i++)
        for (int edge = points[res[i]]; edge != -1; edge = next[edge])
            dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}

int main()
{
    memset(points, -1, sizeof(points));
    memset(to, -1, sizeof(to));
    memset(indeg, 0, sizeof(indeg));
    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b, add_edge(a, b);
        indeg[b] += 1;
    }
    toposort();
    DP();
    for (int i = 1; i <= n; i++)
        cout << dp[i] << endl;
    return 0;
}

P1122:最大子树和题解

思路

设一个F[n+1]为树形DP的数组。在点i上,对于每一个子节点j,都有F[j] = dis[i] + max(0, F[j])。其中dis是美丽指数。

代码

// P1122.cpp
#include <iostream>
#include <algorithm>

using namespace std;
// the tree;
const int maxn = 160010;
int n;
int dis[maxn];
int to[maxn];
int next[maxn];
int point[maxn];
int current = 0;
int F[maxn];
int ans = 0;

void add_edge(int src, int dst)
{
    next[current] = point[src];
    to[current] = dst;
    point[src] = current;
    current++;
}
// core code: search subtrees and add them up to F[curt],
// in the meanwhile, get the ans;
void DFS(int curt, int fat)
{
    F[curt] = dis[curt];
    for (int i = point[curt]; i != -1; i = next[i])
    {
        int dst = to[i];
        if (dst == fat)
            continue;
        DFS(dst, curt);
        F[curt] += max(0, F[dst]);
    }
    ans = max(ans, F[curt]);
}
// initialize;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> dis[i];
    fill(point, point + n + 1, -1);
    fill(next, next + n + 1, -1);
    fill(F, F + n + 1, 0);
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        add_edge(a, b), add_edge(b, a);
    }
    DFS(1, 0);
    cout << ans;
    return 0;
}