[SHOI2017]摧毁“树状图”

每个输入文件包含多个输入数据。输入文件的第一行为两个整数 T 和 x， T 表示该文件包含的输入数据个数， x 的含义见上述。（同一个输入文件的所有数据的 x 都是相同的）

接下来依次输入每个数据。

每个数据的第一行有若干个整数：

若 x = 0，则该行只有一个整数 n。

若 x = 1，则该行依次有三个整数 n, p₀, p₁。

若 x = 2，则该行依次有五个整数 n, p₀, p₁, h₀, h₁。保证 p₀, p₁, h₀, h₁ 均为不超过 n 的正整数。

每个数据接下来有 n 1 行，每行有两个不超过 n 的正整数，表示这两个编号的计算节点之间有一条网线将其相连。保证输入的是一棵树。同一行相邻的整数之间用恰好一个空格隔开。

对于整数 k，设 ∑ n^k 为某个输入文件中，其 T 个输入数据的 n^k 之和。

所有输入文件满足 T ≤ 10^5, ∑ n^1 ≤ 5 × 10^5。

数据文件可能较大，请避免使用过慢的输入输出方法。

C++(clang++11) 解法, 执行用时: 150ms, 内存消耗: 9528K, 提交时间: 2020-11-14 10:52:03

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

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, INF = 0x0f0f0f0f;
int x, n, p0, p1, h0, h1;

struct Edge {
    Edge *next;
    int to;
    Edge(Edge *next = NULL, int to = 0) : next(next), to(to) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];

int f[MAX_N][6], cnt[MAX_N];

void dfs(int u, int fa) {
    cnt[u] = -1;
    for (Edge *e = first[u]; e; e = e->next)
        if (e->to != fa) ++cnt[u], dfs(e->to, u);
}

inline void tension(int &a, const int &b) {
    if (b > a) a = b;
}

void dp(int u, int fa) {
    memset(f[u], -0x3f, sizeof f[u]);
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) dp(e->to, u);

    // f[u][0] 向上
    f[u][0] = cnt[u]; // 单独 
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][0], f[e->to][0] + cnt[u]);

    // f[u][1] 有一个完整的，不包含 u
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][1], f[e->to][2] + 1), tension(f[u][1], f[e->to][1]);

    // f[u][2] 有一个完整的，包含 u
    int mx1 = 0;
    f[u][2] = cnt[u] + 1;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][2], mx1 + f[e->to][0] + cnt[u] + 1);
        tension(mx1, f[e->to][0]);
    }

    // f[u][3] 有一个完整的，且向上
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) // 继承
        tension(f[u][3], f[e->to][3] + cnt[u]);

    // 完整的在下面
    int mx2 = 0;
    mx1 = -INF;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][3], mx1 + f[e->to][0] + cnt[u]);
        tension(f[u][3], f[e->to][1] - 1 + mx2 + cnt[u]);
        tension(f[u][3], f[e->to][2] - 1 + mx2 + cnt[u]);
        tension(mx1, f[e->to][1] - 1), tension(mx1, f[e->to][2] - 1);
        tension(mx2, f[e->to][0]);
    }

    // 交于一点
    int mx3 = 0;
    mx1 = mx2 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        int v = f[e->to][0];
        if (v > mx1) swap(mx1, v);
        if (v > mx2) swap(mx2, v);
        if (v > mx3) swap(mx3, v);
    }
    tension(f[u][3], mx1 + mx2 + cnt[u] + mx3);

    // f[u][4] 有两个完整的，不包含 u
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa)
        tension(f[u][4], f[e->to][5] + 1), tension(f[u][4], f[e->to][4]);
    // 两边继承
    mx1 = -INF, mx2 = -INF;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][4], f[e->to][1] + mx1 - 1);
        tension(f[u][4], f[e->to][1] + mx2);
        tension(f[u][4], f[e->to][2] + mx1);
        tension(f[u][4], f[e->to][2] + mx2 + 1);
        tension(mx1, f[e->to][1]), tension(mx2, f[e->to][2]);
    }

    // f[u][5] 有两个完整的，包含 u
    // 封笔
    mx1 = -INF, mx2 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        tension(f[u][5], mx1 + f[e->to][0] + cnt[u] + 1);
        tension(f[u][5], f[e->to][3] + mx2 + cnt[u] + 1);
        tension(mx1, f[e->to][3]), tension(mx2, f[e->to][0]);
    }
    // 全部在 u 上
    int mx4 = 0;
    mx1 = mx2 = mx3 = 0;
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        int v = f[e->to][0];
        if (v > mx1) swap(mx1, v);
        if (v > mx2) swap(mx2, v);
        if (v > mx3) swap(mx3, v);
        if (v > mx4) swap(mx4, v);
    }
    tension(f[u][5], mx1 + mx2 + mx3 + mx4 + cnt[u] + 1);

    vector<int> vec;
    vec.push_back(-1);
    for (Edge *e = first[u]; e; e = e->next) if (e->to != fa) vec.push_back(e->to);

    int sz = vec.size();
    static int pre[MAX_N], suf[MAX_N], prepre[MAX_N], sufsuf[MAX_N];
    pre[0] = prepre[0] = suf[sz] = sufsuf[sz] = 0;
    for (int i = 1; i < sz; ++i) {
        prepre[i] = max(prepre[i - 1], f[vec[i]][0] + pre[i - 1]);
        pre[i] = max(pre[i - 1], f[vec[i]][0]);
    }
    for (int i = sz - 1; i >= 1; --i) {
        sufsuf[i] = max(sufsuf[i + 1], f[vec[i]][0] + suf[i + 1]);
        suf[i] = max(suf[i + 1], f[vec[i]][0]);
    }
    for (int i = 1; i < sz; ++i) {
        int mx = max(f[vec[i]][1], f[vec[i]][2]);
        tension(f[u][5], mx + prepre[i - 1] + cnt[u]);
        tension(f[u][5], mx + sufsuf[i + 1] + cnt[u]);
        tension(f[u][5], mx + pre[i - 1] + suf[i + 1] + cnt[u]);
    }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    int caseNum = readInt();
    x = readInt();

    while (caseNum--) {
        n = readInt();
        if (x >= 1) p0 = readInt() - 1, p1 = readInt() - 1;
        if (x == 2) h0 = readInt() - 1, h1 = readInt() - 1;

        pit = pool;
        for (int i = 0; i < n; ++i) first[i] = NULL;
        for (int i = 0; i < n - 1; ++i) {
            int u = readInt() - 1, v = readInt() - 1;
            first[u] = new (pit++) Edge(first[u], v);
            first[v] = new (pit++) Edge(first[v], u);
        }

        dfs(0, -1);
        dp(0, -1);

        printf("%d\n", max(f[0][4], f[0][5]));
    }

    return 0;
}

详情