Tree Compass（ Codeforces Round 934 (Div. 2) ）

Tree Compass（ Codeforces Round 934 (Div. 2) ）

Example

Input

4121 241 21 31 472 73 26 45 71 66 7

Output

1
1 0
2
1 1
2 1
2
1 1
2 1
3
6 1
7 1
2 1

Note

In the first test case, there is only one possible operation, and performing it gives us a valid answer.

In the second test case, the first operation colors vertex $2$ black, and the second operation colors vertex $1$ black. It can be shown that it is impossible to color both vertices black in one operation, so the minimum number of operations needed is $2$. Another possible solution is to use the $2$ operations: $(u,r)=(1,0)$ and $(u,r)=(2,0)$.

In the third test case, the first operation colors vertices $2$, $3$ and $4$ black, and the second operation colors vertex $1$ black. Again, it can be shown that it is impossible to color all vertices black in $1$ operation, so the minimum number of operations needed is $2$.

In the fourth test case, the first operation colors vertices $4$, $1$ and $7$ black, the second operation colors vertices $2$, $5$ and $6$ black while the third operation colors vertices $3$ and $7$ black. Notice that it is allowed to color vertex $7$ black twice.

Thus, each node was marked at least once, with node $7$ marked twice. It can be shown that it is impossible to color all vertices black in fewer than $3$ moves.

题解进一步分析和拓展

这个问题的关键在于树的直径，即树中两个最远节点之间的路径长度。直径的长度和树的染色策略有很大关系。接下来我们详细分析如何利用直径的性质优化我们的染色操作，并提出最优的染色方案。

一、直径链的染色操作

考虑一条长度为 (d) 的链，链上的每个节点都需要染色，操作一次最多能染黑链上的 2 个点。我们从树的直径出发，考虑如何使用最少的操作将所有节点染黑。

1. 直径 (d) 为奇数

• 当直径 (d) 是奇数时，我们可以选择直径的中点 (u)，然后进行一系列操作，操作的顺序是从 (u) 出发，染色 (u) 和与其距离为 (0, 1, 2, …, d-1) 的节点。这些操作的形式可以是：

  [
  (u, 0), (u, 1), (u, 2), …, (u, d-1)
  ]

  这样，通过最多 ( \frac{d+1}{2} ) 次操作，所有节点都能被染黑，因为每次操作都会把 2 个点染黑。

2. 直径 (d) 为偶数

• 当直径 (d) 为偶数时，我们面临的挑战是如何通过最少次数的操作，覆盖整棵树的所有节点。这里分为两种情况：

  • 当 (d \mod 4 = 0)（即直径长度为 4 的倍数）：
    我们可以选择直径的中心边 ( (x, y) )，然后交替地进行以下操作：

    [
    (x, 1), (y, 1), (x, 3), (y, 3), …, (x, d/2 - 1), (y, d/2 - 1)
    ]

    这样只需要 ( \frac{d}{2} ) 次操作。

  • 当 (d \mod 4 = 2)（即直径长度为 2 或 6 的余数为 2）：
    由于不能完全通过交替操作来染色，我们只能从中心出发，进行如下操作：

    [
    (x, 0), (x, 1), (x, 2), …, (x, d/2)
    ]

    这样需要 ( \frac{d}{2} + 1 ) 次操作。

二、整体思路

1. 找直径：

   • 通过两次 DFS 来找到树的直径。第一次 DFS 从任意节点出发，找到最远的节点 (A)；第二次 DFS 从 (A) 开始，找到最远的节点 (B)，则 (A) 到 (B) 的路径即为树的直径。

2. 根据直径的长度选择操作策略：

   • 如果直径 (d) 为奇数，从中点出发进行操作。
   • 如果直径 (d) 为偶数，分为两种情况：
     • 如果 (d \mod 4 = 0)，通过中心边交替操作。
     • 如果 (d \mod 4 = 2)，从中心出发逐渐染色。

3. 输出操作结果：

   • 输出最少的操作次数和每次操作的具体节点及距离。

三、时间复杂度分析

• DFS 查找直径的时间复杂度是 (O(n))，每次 DFS 都需要遍历整个树的节点和边，最多遍历 (n-1) 条边。
• 操作计算 的时间复杂度是 (O(1))，因为操作次数由直径的长度确定，而直径已经通过 DFS 计算出来。
• 因此，每个测试用例的时间复杂度是 (O(n))，而给定 (T) 个测试用例，所有测试用例的总时间复杂度为 (O(T \cdot n))。题目保证了总节点数 (n) 不超过 2000，所以这是一个高效的解法。

四、代码实现

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 10;

int n;
vector<int> g[N];
int fa[N];
int started;
int ended;
int height;
vector<int> rode;

void dfs1(int x, int f, int h)
{
    for (auto it : g[x])
    {
        if (it == f)
        {
            continue;
        }
        dfs1(it, x, h + 1);
    }
    if (h > height)
    {
        height = h;
        started = x;
    }
}

void dfs2(int x, int f, int h)
{
    fa[x] = f;
    for (auto it : g[x])
    {
        if (it == f)
        {
            continue;
        }
        dfs2(it, x, h + 1);
    }
    if (h > height)
    {
        height = h;
        ended = x;
    }
}

void cleared()
{
    for (int i = 0; i <= n; ++i)
    {
        g[i].clear();
        fa[i] = 0;
    }
    height = 0;
    rode.clear();
}

void solved()
{
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1, 0, 1);
    // cout << started << endl;
    height = 0;
    dfs2(started, 0, 1);

    int now = ended;
    while (now != 0)
    {
        rode.push_back(now);
        now = fa[now];
    }
    // cout << ended << endl;
    // for (auto it : rode)
    // {
    //     cout << it << ' ';
    // }
    // cout << endl;

    if (height % 2 == 1)
    {
        cout << height / 2 + 1 << endl;
        for (int i = 0; i <= height / 2; ++i)
        {
            cout << rode[height / 2] << ' ' << i << endl;
        }
    }
    else if (height % 4 == 0)
    {
        cout << height / 2 << endl;
        for (int i = 1; i <= height / 2 - 1; i += 2)
        {
            cout << rode[height / 2 - 1] << ' ' << i << endl;
            cout << rode[height / 2] << ' ' << i << endl;
        }
    }
    else
    {
        cout << height / 2 + 1 << endl;
        for (int i = 0; i <= height / 2; i++)
        {
            cout << rode[height / 2 - 1] << ' ' << i << endl;
        }
    }

    cleared();
}

signed main()
{
    BoBoowen;

    int T = 1;
    cin >> T;
    while (T--)
    {
        solved();
    }
}

五、总结

• 树的直径是这道题的核心，利用树的直径来优化染色操作，可以大幅减少操作次数。
• 根据直径的长度，决定从中点出发进行染色或者采用交替操作，这样能够保证染色的最优性。
• 时间复杂度为 (O(n))，对于每个测试用例能够在合理时间内求解出最少的染色操作次数。