【根号分治】CF1790 F

浅浅的花香味﹌ 2024-03-22 20:21 98阅读 0赞

[Problem - F - Codeforces][]

题意：

![d39e51cdfd9b4fc1a390989f342b113c.png][]

思路：

![8805b7c9f6cc400fa0c279c1a92edae5.png][]

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    void solve() {
        int n;
        std::cin >> n;
        
        std::vector<int> c(n);
        for (int i = 0; i < n; i++) {
            std::cin >> c[i];
            c[i]--;
        }
        
        std::vector<std::vector<int>> adj(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            std::cin >> u >> v;
            u--, v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        std::vector<int> dis(n, n);
        int ans = n;
        for (int i = 0; i < n; i++) {
            ans = std::min(ans, dis[c[i]]);
            if (i > 0) {
                std::cout << ans << " \n"[i == n - 1];
            }
            std::queue<int> q;
            q.push(c[i]);
            dis[c[i]] = 0;
            
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                
                for (auto y : adj[x]) {
                    if (dis[x] + 1 < dis[y] && dis[x] + 1 < ans) {
                        dis[y] = dis[x] + 1;
                        q.push(y);
                    }
                }
            }
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t;
        std::cin >> t;
        
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1790/problem/F
[d39e51cdfd9b4fc1a390989f342b113c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/df5f7e134c954c24b6bc375e13a6bf40.png
[8805b7c9f6cc400fa0c279c1a92edae5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4c9b6102ce7f44b3874df81cfdac9514.png