题目分析

这是一个树形结构上的优化问题。需要选择一名负责人，然后通过交换操作最大化团队人数，同时最小化交换次数。

关键约束：

• 选择负责人后，其子树中所有相同编程语言的员工加入
• 可以通过交换增加团队成员
• 交换必须发生在同一深度的员工之间
• 一个在子树内但语言不同，一个在子树外但语言相同

算法思路

核心思想

使用DSU on Tree（树上启发式合并）+ 深度统计：

1. 预处理：计算每个节点的深度、子树大小、DFS序
2. 深度分布统计：统计每种语言在每个深度的员工数量
3. DSU on Tree：高效统计子树信息
4. 贪心计算：对于每个可能的负责人，计算最大团队人数和最少交换次数

关键观察

• 如果选择节点 x 作为负责人，深度为 d
• 那么在深度 d' ≥ d 的层，最多能获得 min(该语言在深度d'的人数, 该深度总人数) 个该语言的员工
• 交换次数 = 总获得人数 - 子树内原有该语言人数

代码详解

数据结构定义

int n, k, a[100100];          // a[i]: 员工i的编程语言（1-indexed）
int head[101000], tot;        // 邻接表头
int idl[100100], idr[100100]; // DFS序区间
int rk[100100];               // 反向映射：DFS序->节点编号
int deep[100100];             // 深度
int son[100100], siz[100100]; // 重儿子、子树大小
int in[101000];               // 当前子树中每种语言的人数
int mp[100100];               // 当前子树中每个深度的人数
int vis[100100];              // 语言访问标记
int ansx, ansy;               // 答案：最大人数、最少交换次数
vector<pair<int, int>> g[101000]; // g[lang]: {(深度, 该深度该语言人数)}

第一次DFS：预处理

void dfs(int x, int fa) {
    idl[x] = ++cnt;           // 进入时间
    rk[cnt] = x;              // 反向映射
    siz[x] = 1;
    deep[x] = deep[fa] + 1;
    
    // 记录该语言的深度分布
    g[a[x]].push_back({deep[x], 1});
    
    int maxx = 0;
    
    for (int i = head[x]; i; i = edge[i].nxt) {
        int y = edge[i].to;
        if (y == fa) continue;
        
        dfs(y, x);
        siz[x] += siz[y];
        
        // 找重儿子（子树最大的儿子）
        if (maxx < siz[y]) {
            maxx = siz[y];
            son[x] = y;
        }
    }
    
    idr[x] = cnt;  // 离开时间
}

语言深度统计的压缩

for (int i = 1; i <= k; i++) {
    sort(g[i].begin(), g[i].end());  // 按深度排序
    
    st.clear();
    // 合并相同深度的记录
    for (pair<int, int> op : g[i])
        if (st.empty() || st.back().x != op.x)
            st.push_back(op);
        else
            st.back().y++;
    
    swap(st, g[i]);  // 更新为压缩后的结果
}

结果：g[lang] 变为按深度排序的列表，每个元素是 (深度, 该深度该语言人数)

第二次DFS：DSU on Tree

void dfs2(int x, int fa, int op) {
    // op=1表示保留信息，op=0表示清除信息
    
    vis[a[x]]++;  // 标记当前语言被访问
    
    // 1. 先处理轻儿子（清除模式）
    for (int i = head[x]; i; i = edge[i].nxt) {
        int y = edge[i].to;
        if (y == fa || y == son[x]) continue;
        dfs2(y, x, 0);
    }
    
    // 2. 处理重儿子（保留模式）
    if (son[x]) dfs2(son[x], x, 1);
    
    // 3. 添加当前节点信息
    mp[deep[x]]++;      // 深度计数+1
    in[a[x]]++;         // 当前语言计数+1
    
    // 4. 合并轻儿子的信息
    for (int i = head[x]; i; i = edge[i].nxt) {
        int y = edge[i].to;
        if (y == fa || y == son[x]) continue;
        
        // 遍历轻儿子的整个子树
        for (int j = idl[y]; j <= idr[y]; j++) {
            int node = rk[j];
            mp[deep[node]]++;
            in[a[node]]++;
        }
    }
    
    // 5. 计算结果（以x为负责人）
    vis[a[x]]--;
    if (!vis[a[x]]) {  // 如果当前语言没有被访问过（避免重复计算）
        int ans = 0, sum = 0;
        int lang = a[x];
        int depth = deep[x];
        
        // 二分找到深度≥depth的位置
        int b = lower_bound(g[lang].begin(), g[lang].end(), 
                           make_pair(depth, 0)) - g[lang].begin();
        
        // 计算最大可能人数
        for (int i = b; i < g[lang].size(); i++) {
            int dep = g[lang][i].x;
            int cnt_lang = g[lang][i].y;      // 该语言在该深度的人数
            int cnt_total = mp[dep];          // 该深度的总人数
            ans += min(cnt_lang, cnt_total);  // 最多能获得的人数
        }
        
        // 交换次数 = 总获得人数 - 子树内原有该语言人数
        sum = ans - in[lang];
        
        // 更新答案
        if (ansx < ans) {
            ansx = ans;
            ansy = sum;
        } else if (ansx == ans && ansy > sum) {
            ansy = sum;  // 人数相同，取更少交换次数
        }
    }
    
    // 6. 如果是轻儿子，清除信息
    if (!op) {
        for (int i = idl[x]; i <= idr[x]; i++) {
            int node = rk[i];
            mp[deep[node]]--;
            in[a[node]]--;
        }
    }
}

算法原理

DSU on Tree 的优势

普通的暴力做法需要对每个节点遍历其子树，复杂度 O(n²)。

DSU on Tree 通过：

1. 重儿子保留：重儿子的信息不清除，直接继承
2. 轻儿子合并：轻儿子的信息单独计算后合并
3. 复杂度优化：从 O(n²) 降到 O(n log n)

最大人数的计算逻辑

对于负责人 x（深度为 d，语言为 L）：

1. 在深度 d' ≥ d 的层：

   • 该层总共有 mp[d'] 个员工（在x的子树中）
   • 整个公司有 cnt_lang 个语言L的员工在该层
   • 最多能获得 min(mp[d'], cnt_lang) 个语言L的员工

2. 为什么？因为：

   • 最多只能有 mp[d'] 个位置（子树内的位置）
   • 最多只有 cnt_lang 个该语言的员工
   • 通过交换，可以用子树外的该语言员工替换子树内的其他语言员工

最少交换次数的计算

• in[lang]：子树内原有该语言人数
• ans：最终能获得的总人数
• 交换次数 = ans - in[lang]

解释：需要把 ans - in[lang] 个该语言的员工从子树外交换进来

复杂度分析

时间复杂度

• 第一次DFS：O(n)
• 语言统计压缩：O(n log n)（排序）
• 第二次DFS：O(n log n)（DSU on Tree）
• 总复杂度：O(n log n)

空间复杂度

• 邻接表：O(n)
• 各种数组：O(n)
• 语言深度统计：O(n)

样例分析

样例3执行过程

输入：

9 3
0 0 2 1 2 0 2 1 2
4 8 1 0 4 1 0 7

算法步骤：

1. DFS预处理，计算深度、重儿子等
2. 统计每种语言的深度分布
3. DSU on Tree计算每个节点作为负责人的结果
4. 发现以节点4为负责人最优：
   • 最大人数：4
   • 最少交换次数：2

关键技巧

1. DFS序转换：将子树操作转化为区间操作
2. 重链剖分：实现DSU on Tree的基础
3. 深度分层统计：处理交换的深度约束
4. 语言压缩：合并相同深度的记录，优化查询
5. 贪心选择：在人数相同时选择交换次数少的方案