USACO 2019 Platinum Bessie's Snow Cow 题解

题目分析

这道题要求维护一棵树，支持两种操作：

1. 将某个节点及其子树染上一种颜色
2. 查询某个节点子树中所有节点的颜色种类数之和

关键点：

• 染色操作影响整个子树
• 每个节点可能被多次染色，需要维护颜色集合
• 需要高效支持子树查询

解题思路

核心观察

1. 染色特性：染色操作作用于整个子树
2. 颜色覆盖：如果节点 u 被染色 c，那么整个 u 的子树都会被染上 c
3. 去重优化：如果某个节点已经被包含在更大范围的同色染色中，可以忽略当前操作

算法设计

代码采用了DFS序 + 线段树 + 集合维护的方法：

主要组件：

1. DFS序：将树结构转化为线性序列，便于处理子树
2. 线段树：维护区间和，支持区间加和区间查询
3. 颜色集合：对每种颜色维护已染色的区间集合

代码详解

#include "bits/stdc++.h"
using namespace std;

const int N = 1e5 + 5;
int n, q;
int tin[N], tout[N], t = 0;  // DFS时间戳
vector<int> adj[N];

// DFS预处理，计算每个节点的进出时间
void dfs(int u, int p = 0) {
    tin[u] = ++t;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    tout[u] = t;
}

// 线段树，支持区间加和区间查询
struct ST {
    ll st[N << 2], data[N << 2];  // st: 区间和, data: 懒标记
    
    void update(int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        
        if (l >= u && r <= v) {
            st[id] += (ll)(r - l + 1) * val;
            data[id] += val;
            return;
        }
        
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1] + (r - l + 1) * data[id];
    }
    
    ll get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        
        if (l >= u && r <= v) return st[id];
        
        int mid = (l + r) >> 1;
        int L = max(l, u), R = min(r, v);
        return get(id << 1, l, mid, u, v) + 
               get(id << 1 | 1, mid + 1, r, u, v) + 
               (R - L + 1) * data[id];
    }
} st;

// 对每种颜色维护已染色的区间集合
set<pii> s[N];

// 染色操作
void update(int u, int c) {
    int l = tin[u], r = tout[u];
    
    // 检查是否已经被包含在更大的同色区间中
    auto it = s[c].lower_bound({l, 0});
    if (it != s[c].begin()) {
        auto prev_it = prev(it);
        if (l >= prev_it->first && r <= prev_it->second) {
            return;  // 已经被覆盖，跳过
        }
    }
    
    // 移除被当前区间包含的旧区间
    for (auto it = s[c].lower_bound({l, 0}); 
         it != s[c].end() && it->first <= r; ) {
        // 从线段树中移除旧区间的影响
        st.update(1, 1, t, it->first, it->second, -1);
        it = s[c].erase(it);
    }
    
    // 添加新区间
    s[c].insert({l, r});
    st.update(1, 1, t, l, r, 1);
}

void solve() {
    dfs(1);
    
    while (q--) {
        int type, u, c;
        cin >> type >> u;
        
        if (type == 1) {
            cin >> c;
            update(u, c);
        } else {
            // 查询子树颜色丰富度之和
            cout << st.get(1, 1, t, tin[u], tout[u]) << endl;
        }
    }
}

算法原理

1. DFS序转换

通过DFS遍历，将树结构转化为线性序列：

• tin[u]: 节点 u 的进入时间
• tout[u]: 节点 u 的离开时间
• 节点 u 的子树对应区间 [tin[u], tout[u]]

2. 颜色维护策略

对每种颜色 c，维护一个区间集合 s[c]，存储该颜色已经覆盖的区间。

关键优化：

• 区间合并：如果新染色区间包含旧区间，移除旧区间
• 去重检查：如果当前操作区间已被包含，直接跳过

3. 线段树作用

线段树维护每个位置的颜色数量：

• update: 区间加操作，表示这些节点新增一种颜色
• get: 区间求和，计算子树颜色丰富度之和

复杂度分析

• 时间复杂度：
  • 每次染色操作最坏 $O(\log n + k\log n)$，其中 $k$ 是移除的区间数
  • 查询操作 $O(\log n)$
• 空间复杂度：$O(n + q)$

样例解析

以样例中的操作为例：

1. 1 4 1: 将节点4及其子树染颜色1

   • 区间: [tin[4], tout[4]] = [4,4]
   • 线段树: 位置4的值+1

2. 2 1: 查询节点1的子树

   • 区间: [1,5]
   • 求和: 只有位置4有颜色，返回1

3. 1 5 1: 将节点5及其子树染颜色1

   • 区间: [5,5] 被 [4,5] 包含？需要检查

关键技巧

1. DFS序应用：将子树操作转化为区间操作
2. 集合维护：用set高效管理颜色区间
3. 懒标记线段树：高效支持区间修改和查询
4. 去重优化：避免重复染色，提高效率

总结

这道题的解题亮点：

1. 问题转化：将树上的子树操作转化为序列上的区间操作
2. 数据结构组合：结合线段树和set处理区间覆盖问题
3. 优化策略：通过区间包含检查避免重复操作
4. 高效查询：利用线段树快速回答子树查询

算法通过巧妙的数据结构设计，在 $O((n+q)\log n)$ 时间内解决了大规模树的染色查询问题，展示了处理树上区间操作的高级技巧。