专栏文章

题解：AT_abc394_f [ABC394F] Alkane

__Linver_
AT_abc394_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq5mg5c
此快照首次捕获于
2025/12/03 23:20
3 个月前
此快照最后确认于
2025/12/03 23:20
3 个月前
查看原文

定义

对每个非根节点 vv，dpvdp_v 表示以 vv 为根的子树中，添加 vv 后形成烷的最大顶点数。

转移

若 vv 度数大于等于 11，则 dpv=1dp_v = 1（仅包含 vv 和其父节点）。
若 vv 度数大于等于 44，需要 33 个子节点：选 33 个 dpudp_u 最大的子节点 u1,u2,u3u_1, u_2, u_3，用 dpu1+dpu2+dpu3+1dp_{u_1} + dp_{u_2} + dp_{u_3} + 1 更新。
枚举每个顶点 vv 作为最深顶点：若 vv 度数为 11，用 dpu+1dp_u + 1（uu 是 vv 的父节点）更新。
若 vv 度数大于等于 44，用 dpu1+dpu2+dpu3+dpu4+1dp_{u_1} + dp_{u_2} + dp_{u_3} + dp_{u_4} + 1（u1,u2,u3,u4u_1, u_2, u_3, u_4 是 vv 的子节点）更新。
取所有情况的最大值。
CPP
#include <bits/stdc++.h>
// #include <atcoder/all>
// #define int long long
using namespace std;
inline int read()
{
    int f = 0, ans = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= c == '-', c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
constexpr int N = 2e5 + 5;
int n, ans, f[N];
vector<int> g[N];
vector<pair<int, int>> sub_f[N];
void dfs(int u, int fa)
{
    f[u] = 1;
    for (int &v : g[u])
        if (v != fa)
        {
            dfs(v, u);
            sub_f[u].emplace_back(v, f[v]);
        }
    sort(begin(sub_f[u]), end(sub_f[u]), [](auto &x, auto &y)
         { return x.second > y.second; });
    if (size(sub_f[u]) >= 3)
    {
        f[u] += f[sub_f[u][0].first] + f[sub_f[u][1].first] + f[sub_f[u][2].first];
        if (fa)
            ans = max(ans, f[u] + 1);
    }
    if (size(sub_f[u]) >= 4)
    {
        ans = max(ans, 1 + f[sub_f[u][0].first] + f[sub_f[u][1].first] + f[sub_f[u][2].first] + f[sub_f[u][3].first]);
    }
}
void resolve(int u, int fa, int from_fa)
{
    if (fa && f[u] != 1)
        ans = max(ans, f[u] + from_fa);
    if (fa)
        sub_f[u].emplace_back(0, from_fa);
    sort(begin(sub_f[u]), end(sub_f[u]), [](auto &x, auto &y)
         { return x.second > y.second; });
    for (int &v : g[u])
        if (v != fa)
        {
            int sum = 0, cnt = 0;
            for (auto &[i, w] : sub_f[u])
                if (i != v)
                {
                    sum += max(f[i], w);
                    if (++cnt == 3)
                        break;
                }
            if (cnt == 3)
                resolve(v, u, sum + 1);
        }
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    ans = -1;
    dfs(1, 0);
    resolve(1, 0, 0);
    write(ans);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...