# Codeforces 1790 Timofey and Black-White Tree
###### tags: `codeforces` `Tree`

[題目連結](https://codeforces.com/contest/1790/problem/F)

# 題目說明
給定一顆 N個節點的數, 起初有一個初始節點 c1 被染色

接下來 給 n-1個染色的節點, c2, c3, c4... cn

每次有新的染色節點時, 印出在這棵樹上任意兩個染色節點最短的距離.

ex:
染色節點 1, 6 其距離為 3
染色節點 1, 4 其距離為 2
因此在這三個染色點, 最短的距離為 2

:::info
:bulb: **需要的知識**:
在一條長度為n的線段, 放置$\sqrt{n}$個節點, 兩兩之間的距離一定小於等於 $\sqrt{n}$

也就是說 距離最大的情況為 $\sqrt{n}$

對於樹的結構, 也會有相同的特性,
在樹的節點, 擺放 $\sqrt{n}$ 的節點, 兩兩之間的距離一定小於等於 $\sqrt{n}$
:::

:::info
:bulb: 特性 1
假如當前任意兩個染色節點最短距離為 x,
新的點加入時, 該節點到達其他染色距離 只要大於等於 x,
就表示該節點不會影響結果.
:::

# Method DFS
:::info
:bulb: **作法講解**:
變數說明:
min_dist: 維護其他染色節點到達 ith node 所需要的最短距離.
output: 維護當前加入節點的最短距離.

一開始先使用DFS 遍歷 c1 節點 到所有節點的距離,

每次有新染節點(node)加入時,
min_dist[node]的值就表示 node 到 其他最近的染色節點的距離.
更新 output = min(output, min_dist[node])

然後再從node出發, 遍歷node附近的節點, 這邊需要特別注意,
**case 1: 假如新的節點 x 與node 的距離 大於等於 min_dist[x], 表示前面有其他染色節點更靠近x.**

**case 2: 假如新的節點 x 與node 的距離 大於等於 output, 即使更新了其min_dist[x],**
**min_dist[x]對於最終結果也不會有影響**

:::

TC: O(NlogN) SC: O(N)

完整程式碼

int nums[N];
vector<int> adj[N];
int min_dist[N];
void dfs(int node, int parent, int d, int &ans)
{
    if ((d >= min_dist[node]) || (d >= ans)) {
        return;
    }
    min_dist[node] = d;
    for (int next : adj[node]) {
        if (next == parent) {
            continue;
        }
        dfs(next, node, d + 1, ans);
    }
}

void solve(int round)
{
    int n, c;
    int a, b;
    int output = INT32_MAX;

    for (int i = 0; i < N; i++) {
        adj[i].clear();
    }
    CLR(nums);
    SET(min_dist, 0x3f);

    cin >> n >> c;

    for (int i = 1; i < n; i++) {
        cin >> nums[i];
    }

    for (int i = 0; i < n-1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(c, -1, 0, output);

    for (int i = 1; i < n; i++) {
        output = min(output, min_dist[nums[i]]);
        printf("%d ", output);
        dfs(nums[i], -1, 0, output);
    }
    printf("\n");
}