2021 CCPC 网络赛重赛 Jumping Monkey（并查集重构树，dfs）

题目链接

给出一个 n n n个结点的树，每个节点有一个权值 a i a_i ai​。现在有一个猴子，他可以从 i i i结点跳到 j j j结点的要求是：在 i i i-> j j j的最短路径上 j j j的权值是最大的。现在询问 k ⊆ ( 1 , n ) k subseteq (1, n) k⊆(1,n)时，猴子能跳到的最多结点数量。

#include
#define int long long
#define endl 'n' 
using namespace std;
typedef pair PII;
const int N = 1e5 + 10;
vector G[N]; // 原树
vector NG[N]; // 新树

int depth[N]; // 答案
int p[N];
int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u)
{
    for(auto &j : NG[u])
    {
        depth[j] = depth[u] + 1;
        dfs(j);
    }
}

signed main(){
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int T; scanf("%lld", &T);
    while(T -- )
    {
        int n; scanf("%lld", &n);
        for(int i = 0; i <= n; ++i)
        {
            NG[i].clear(); G[i].clear();
            p[i] = i; depth[i] = 0;
        }
        PII a[n + 1];
        vector vis(n + 1, false);
        for(int i = 1; i < n; ++i)
        {
            int x, y;scanf("%lld%lld", &x, &y);
            G[x].push_back(y); 
            G[y].push_back(x);
        }
        for(int i = 1; i <= n; ++i)
        {
            int x; scanf("%lld", &x);
            a[i] = {x, i};
        }
        sort(a + 1, a + 1 + n);
        vis[a[1].second] = true;
        for(int i = 2; i <= n; ++i)
        {
            int u = a[i].second;
            for(auto &j : G[u])
            {
                if(!vis[j]) continue; // 连接相关边
                int v = find(j);  // 连向该联通块的跟结点
                p[v] = u;
                NG[u].push_back(v);
            }
            vis[u] = true;
        }
        depth[a[n].second] = 1;
        dfs(a[n].second);
        for(int i = 1; i <= n; ++i) cout << depth[i] << endl;
    }
    return 0;
}