算法

转化题意, 即为

求树上最长不重链覆盖

长链剖分

显然可以使用长链剖分的思想, 直接剖分后贪心的求最大链即可

代码

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

#define ll long long
const int maxn = 1e5 + 5;
int n, u, v, rt, d[maxn], son[maxn], h[maxn];
int head[maxn], cnt;
struct edge
{
    int to, next;
} e[maxn << 1];
vector<int> val;

void adde(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void dfs1(int u, int fa)
{
    d[u] = d[fa] + 1;
    int num = 0;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs1(v, u);
        num++;
    }
    if (!num)
    {
        if (!rt || d[u] >= d[rt])
            rt = u;
    }
}

void dfs2(int u, int fa)
{
    d[u] = d[fa] + 1;
    h[u] = d[u];
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs2(v, u);
        h[u] = max(h[u], h[v]);
        if (!son[u])
            son[u] = v;
        else if (h[son[u]] < h[v])
            son[u] = v;
    }
}

void dfs3(int u, int fa, int tp)
{
    if (!son[u])
    {
        val.push_back(d[u] - d[tp]);
        return;
    }
    dfs3(son[u], u, tp);
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        if (v == son[u])
            continue;
        dfs3(v, u, u);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        adde(u, v);
        adde(v, u);
    }
    rt = 0;
    ll ans = 0;
    dfs1(1, 0);
    dfs2(rt, 0);
    dfs3(rt, 0, 0);
    printf("1 ");
    sort(val.begin(), val.end(), greater<int>());
    for (int i = 2; i <= n; i++)
    {
        if (i - 2 < val.size())
            ans += val[i - 2];
        printf("%lld ", ans);
    }
    return 0;
}

总结

善于转化题意, 可以简化做题

线段树上二分

观察题目

\(k = 1\) 时, 答案为 \(1\)
\(k = 2\) 时, 答案为 树的直径的长度

\(k = 3, 4, 5 \cdots\) 时, 答案为距离已被染色的点最远的未被染色的点在染色链的长度

又容易发现当以直径的一端为根节点时, 当一个点没有被染色时, 其子树一定也没被染色
所以考虑使用线段树维护每个点距离已经染色过的点的最近距离

每次在线段树上二分查找最近距离最远的点, 然后染色(注意用线段树维护树, 类似于树链剖分的思想, 使用 dfn 序维护), 注意自己未被染色时, 距离未被染色的点至少为 \(1\), 最初建立线段树时要做一遍 dfs , 找到每个点与根节点的最短距离
注意在染色之后, 要一直沿着向上的链找第一个染色的 \(father\) 节点, 在向上的过程中, 将途经的点距离已经染色过的点的最近距离修改为 \(0\), 将其(这里指途经的点)子树距离染色过的点的最短距离修改为其(这里指子树的点)原本距离 - \(1\) [自己(这里指子树上的点)还未染色]

即为

        int u = id[binary(1)];
        if (mrk[u])
            break;
        while (!mrk[u])
        {
            int Val = query(1, app[u]);
            modify(1, app[u], app[u], Val);
            for (int k : G[u])
                if (k != fa[u] && !mrk[k])
                {
                    int val = query(1, app[k]);
                    modify(1, app[k], app[k] + siz[k] - 1, val - 1);
                }
            mrk[u] = true, u = fa[u];
            ++ans;
        }

代码

没时间写了, 什么时候把 lhs 解决掉才能写这种题(

#include <cstdio>
#include <vector>
#include <algorithm>

using std::max;

const int MAXN = 1e5 + 5;

int n;
int val[MAXN << 1];

std::vector<int> G[MAXN << 1];

int siz[MAXN << 1], fa[MAXN << 1];
int app[MAXN << 1], id[MAXN << 1], cnt;
bool mrk[MAXN << 1];

void dfs(int u, int father)
{
    app[u] = ++cnt, siz[u] = 1, id[cnt] = u;
    if (!mrk[u])
        val[u] = val[fa[u] = father] + 1;
    for (int k : G[u])
        if (k != father)
            dfs(k, u), siz[u] += siz[k];
}

namespace SGT
{
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)

    struct Sgt
    {
        int l, r, mx, tag;
    } tr[MAXN << 2];

    void pushup(int u)
    {
        tr[u].mx = max(tr[ls(u)].mx, tr[rs(u)].mx);
    }

    void upd(int u, int val)
    {
        tr[u].mx -= val, tr[u].tag += val;
    }

    void pushdown(int u)
    {
        upd(ls(u), tr[u].tag), upd(rs(u), tr[u].tag);
        tr[u].tag = 0;
    }

    void build(int u, int l, int r)
    { 
        tr[u].l = l, tr[u].r = r;
        if (l == r)
            return tr[u].mx = val[id[l]], void();
        int mid = l + r >> 1;
        build(ls(u), l, mid), build(rs(u), mid + 1, r);
        pushup(u);
    }

    int binary(int u)
    {
        if (tr[u].l == tr[u].r)
            return tr[u].l;
        pushdown(u);
        return binary(tr[ls(u)].mx > tr[rs(u)].mx ? ls(u) : rs(u));
    }

    void modify(int u, int l, int r, int val)
    {
        if (tr[u].l >= l && tr[u].r <= r)
            return upd(u, val);
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid)
            modify(ls(u), l, r, val);
        else if (l > mid)
            modify(rs(u), l, r, val);
        else
            modify(ls(u), l, r, val), modify(rs(u), l, r, val);
        pushup(u);
    }

    int query(int u, int x)
    {
        if (tr[u].l == tr[u].r)
            return tr[u].mx;
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            return query(ls(u), x);
        else
            return query(rs(u), x);
    }
}
using SGT::modify, SGT::binary, SGT::query;

int rt;
int ans;

namespace D
{
    int st, ed;
    bool flg;
    int mx;

    void dfs1(int u, int father, int dis)
    {
        if (dis > mx)
            mx = dis, st = u;
        for (int k : G[u])
            if (k != father)
                dfs1(k, u, dis + 1);
    }

    void dfs2(int u, int father, int dis)
    {
        if (dis > mx)
            mx = dis, ed = u;
        for (int k : G[u])
            if (k != father)
                dfs2(k, u, dis + 1);
    }

    void DFS(int u, int father, int ed)
    {
        mrk[u] = true;
        if (u == ed)
            return flg = true, void();
        for (int k : G[u])
            if (k != father)
            {
                DFS(k, u, ed);
                if (flg)
                    return;
            }
        mrk[u] = false;
    }

    void Get()
    {
        dfs1(1, 0, 1), mx = 0, dfs2(st, 0, 1), DFS(st, 0, ed);
        rt = st, printf("%d ", ans = mx);
    }
}

int main()
{

    scanf("%d", &n);
    if (n == 1)
        return puts("1"), 0;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y), G[y].push_back(x);
    }
    printf("1 ");
    D::Get();
    dfs(rt, 0);
    SGT::build(1, 1, n);
    int cnt = 3;
    for (; cnt <= n; ++cnt)
    {
        int u = id[binary(1)];
        if (mrk[u])
            break;
        while (!mrk[u])
        {
            int Val = query(1, app[u]);
            modify(1, app[u], app[u], Val);
            for (int k : G[u])
                if (k != fa[u] && !mrk[k])
                {
                    int val = query(1, app[k]);
                    modify(1, app[k], app[k] + siz[k] - 1, val - 1);
                }
            mrk[u] = true, u = fa[u];
            ++ans;
        }
        printf("%d ", ans);
    }
    for (; cnt <= n; ++cnt)
        printf("%d%c", n, " \n"[cnt == n]);

    return 0;
}

总结

此题借鉴了树链剖分的思路, 但与树链剖分完全不同
注意树上处理问题时

• 关注深度
• 关注根节点
• 在修改时, 注意子树的变化也需要修改

树上问题中, 线段树可以用来

• 树链剖分, 高效维护一颗树
• \(\log n\) 的寻找一些可并的信息(本题中为 "最近距离最远的点")

代码当然非常难搞, 以后再说