「CF1521D」Nastia Plays with a Tree

发表于 分类于

$Link$

你有一棵 $n$ 个点的树，每次操作你可以删除一条边，再添加一条边（删边加边合起来算一种操作）。

问最少需要多少次操作，可以让这棵树变成一条链，输出方案。

$t$ 组数据。

$1\le t\le10^4,2\le n\le10^5,\sum n\le2\times10^5$。

感觉其实比 $E$ 要难。

总体变成链，可以相当于把树拆成一堆的子链，再把所有子链连起来，于是问题相当于把树拆成尽可能少的链。

随便个点为根，然后从底端，也就是叶子节点往上考虑。

叶子节点就相当于一个点的链，往上推一层，可以发现这个点有两种情况：

  • 在一条从它的子树外到它的子树内的一条链上。
  • 在一条从它的一个儿子的子树内，到它的另一个儿子的子树内的一条链上。

以下我们假设正在处理点 $u$，$u$ 的儿子为 $v_{1,2,\cdots}$，$u$ 的父亲为 $fa_u$。

于是我们可以按照儿子的数量来分类讨论，注意这里我们只考虑所有儿子都是叶子节点的的点的情况，假设现在正在处理点 $u$：

  • 如果 $u$ 只有 $1$ 个儿子，显然直接接进去就行了，不需要操作。
  • 如果 $u$ 有 $2$ 个儿子，为了让链的数量最少，我们使用上述的第二种链。此时我们必须删去边 $fa_u\to u$。
  • 如果 $u$ 有 $>2$ 个儿子，显然我们随便挑两个儿子使用第二种链，剩下的所有儿子，删去边 $u\to v_{3,\cdots,n}$，并把 $v_{3,\cdots,n}$ 依次接入这条链。同样地，我们也要删去边 $fa_u\to u$。

如果只考虑这些点，显然这样连边最优。

把分类推广到所有点？

显然我们应当优先使用第二种链，问题在于这样必须要删掉边 $fa_u\to u$，这样会导致答案变劣吗？

思考一下，对于 $fa_u,u,v_1,v_2$ ，如果我们使用第一种，一共需要三条链；如果使用第二种，那么需要两条链，显然更优。

于是我们记录每个点所在的链的链头和链尾，记为 $head_u,tail_u$，分类变成这样：

  • 如果 $u$ 只有 $1$ 个儿子，$head_u=u,tail_u=tail_{v_1}$。
  • 如果 $u$ 有 $\ge2$ 个儿子，删去边 $fa_u\to u$，$head_u=tail_{v_1},tail_u=tail_{v_2}$，对于剩下的儿子，删去边 $u\to v_{3\cdots n}$，并顺次连接并到这条链上。

就这样？感觉似乎漏了点什么。

确实，对于第二种链，我们还需要把这条链并到他父亲所在的链上，然后就做完了。

时间复杂度 $O(\sum n)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int tt;
int n;
struct Edge {
    int to, next;
} edge[N * 2 + 1];
int start[N + 1], tot;
int head[N + 1], tail[N + 1], deleted[N + 1];
vector<pair<int, int> > del, add;

inline void addedge(int u, int v)
{
    edge[++tot] = { v, start[u] };
    start[u] = tot;
    edge[++tot] = { u, start[v] };
    start[v] = tot;
    return;
}
inline void solve(int u, int fa)
{
    head[u] = tail[u] = u;
    vector<int>sons, delsons;

    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa)
            continue;
        solve(v, u);
        if (!deleted[v]) {
            sons.push_back(v);
        } else {
            delsons.push_back(v);
            del.push_back(make_pair(u, v));
        }
    }
    int h = 0, t = 0;

    if (delsons.size()) {
        h = head[delsons[0]];
        t = tail[delsons[0]];
        for (int i = 1; i < delsons.size(); i++) {
            add.push_back(make_pair(t, head[delsons[i]]));
            t = tail[delsons[i]];
        }
    }
    if (sons.size() == 1) {
        head[u] = u;
        tail[u] = tail[sons[0]];
    }
    if (sons.size() >= 2) {
        head[u] = tail[sons[0]];
        tail[u] = tail[sons[1]];
        for (int i = 2; i < sons.size(); i++) {
            int v = sons[i];
            del.push_back(make_pair(u, v));
            add.push_back(make_pair(tail[u], head[v]));
            tail[u] = tail[v];
        }
        deleted[u] = 1;
    }
    if (h) {
        add.push_back(make_pair(tail[u], h));
        tail[u] = t;
    }
    return;
}
int main()
{
    tt = read();

    while (tt--) {
        add.clear();
        del.clear();
        memset(start, 0, sizeof(int) * (N + 1));
        tot = 0;
        memset(deleted, 0, sizeof(int) * (N + 1));
        n = read();
        for (int i = 1; i < n; i++)
            addedge(read(), read());
        solve(1, 0);
        printf("%d\n", add.size());
        for (int i = 0; i < add.size(); i++)
            printf("%d %d %d %d\n", del[i].first, del[i].second, add[i].first, add[i].second);
    }

    return 0;
}