问题分析

我们需要维护一棵有根树，支持三种操作：

1. 路径重染色：将某个节点到根的路径染成全新颜色
2. 路径查询：查询两点路径上不同颜色的数量
3. 子树查询：查询子树中到根路径颜色数的最大值

核心算法

算法框架：LCT + 树链剖分 + 线段树

使用LCT（Link-Cut Tree）维护树的链结构，结合DFS序和线段树来支持子树查询。

关键数据结构

• LCT节点：维护splay树结构，记录子树大小和顶部节点
• 线段树：维护每个DFS序位置的权值（颜色数）
• 倍增数组：用于LCA查询

算法步骤详解

1. 初始化处理

void dfs(int x) {
    dfn[x] = ++cnt;  // DFS序
    siz[x] = 1;      // 子树大小
    // 预处理倍增数组
    for (int i = 1; i <= 17; i++) 
        f[x][i] = f[f[x][i-1]][i-1];
    
    // 递归处理子树
    for (int y : e[x]) {
        if (y == fa[x]) continue;
        fa[y] = f[y][0] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
        siz[x] += siz[y];
    }
    // 初始化线段树权值
    update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, 1);
}

2. 路径重染色操作

void access(int x) {
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x);
        int z = t[rs].top;
        update(1, 1, n, dfn[z], dfn[z] + siz[z] - 1, 1);  // 移除旧链
        z = t[y].top;
        update(1, 1, n, dfn[z], dfn[z] + siz[z] - 1, -1); // 添加新链
        rs = y;
        pushup(x);
    }
}

access(x)操作将x到根的路径变为偏爱边，相当于重染色。

3. 路径查询操作

int lca = get(x, y);
cout << query(x) + query(y) - query(lca) * 2 + 1 << '\n';

利用公式：路径颜色数 = query(x) + query(y) - 2*query(lca) + 1

4. 子树查询操作

query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1)

直接在DFS序对应的区间查询最大值。

算法标签

• Link-Cut Tree (LCT)
• 树链剖分 (Heavy-Light Decomposition)
• 线段树 (Segment Tree)
• 最近公共祖先 (LCA)
• DFS序 (Euler Tour)

复杂度分析

• 预处理：$O(n \log n)$
• access操作：均摊 $O(\log n)$
• 路径查询：$O(\log n)$
• 子树查询：$O(\log n)$
• 总复杂度：$O((n+m) \log n)$

关键技巧

1. 权值维护原理

每个节点存储的是从该节点到根的路径上的颜色数。当进行access操作时，实际上是在调整偏爱路径，对应颜色数的变化。

2. LCT与线段树的结合

// access时更新线段树
update(1, 1, n, dfn[z], dfn[z] + siz[z] - 1, 1);   // 断开旧链
update(1, 1, n, dfn[z], dfn[z] + siz[z] - 1, -1);  // 连接新链

通过DFS序将LCT的子树操作映射到线段树的区间操作。

3. 路径查询公式推导

对于路径x-y：

• query(x)：x到根的颜色数
• query(y)：y到根的颜色数
• query(lca)：lca到根的颜色数
• 路径颜色数 = query(x) + query(y) - 2*query(lca) + 1

4. 懒标记线段树

void lazy(int x, int v) {
    tr[x].maxn += v;
    tr[x].tag += v;
}

支持区间加和区间最大值查询。

样例验证

对于样例操作序列：

1. 初始查询2 4 5：路径4-3-5，3种颜色 → 输出3
2. 查询3 3：子树中到根路径最大值 → 输出4
3. 重染色1 4：更新路径1-2-3-4
4. 查询2 4 5：路径颜色减少 → 输出2
5. 重染色1 5：更新路径1-2-3-5
6. 查询2 4 5：路径颜色保持 → 输出2

正确性证明

1. access操作正确性：LCT的access操作确保每次重染色只影响一条链。

2. 颜色数维护：线段树正确维护每个节点到根的路径颜色数。

3. 路径查询：利用树的性质和LCA正确计算路径颜色数。

该解法通过LCT动态维护树链结构，结合线段树高效处理子树查询，实现了所有操作的对数时间复杂度。