「Drawing」树平面嵌入题解

问题分析

我们需要将一棵度数最多为3的树嵌入到给定的平面点集中，使得树边对应的线段除端点外不相交。

核心思路

使用分治+几何排序的方法，关键思想是利用树的链结构和点的凸包性质。

算法详解

1. 树的重链分解

Node *BuildTree(int i, int parent) {
    Node *node = node_alloc++;
    node->index = i;
    node->size = 1;
    
    for (vector<int>::iterator it = adj[i].begin(); it != adj[i].end(); ++it) {
        if (*it == parent) continue;
        
        if (!node->left) {
            node->left = BuildTree(*it, i);
            node->left->parent = node;
            node->size += node->left->size;
            node->heavy = node->left;  // 重儿子
        } else {
            node->right = BuildTree(*it, i);
            node->right->parent = node;
            node->size += node->right->size;
            
            if (node->right->size > node->left->size) {
                node->heavy = node->right;  // 选择更大的作为重儿子
            }
        }
    }
    return node;
}

2. 几何比较函数

// 计算有向面积（用于判断点的相对位置）
long long SignedArea(Point const &A, Point const &B, Point const &C) {
    int dx1 = A.x - C.x;
    int dy1 = A.y - C.y;
    int dx2 = B.x - C.x;
    int dy2 = B.y - C.y;
    return (long long)dx1 * dy2 - (long long)dx2 * dy1;
}

// 从凸包点出发的角度比较
struct CmpAngleFromPointOnHull {
    Point const &O;
    CmpAngleFromPointOnHull(Point const &O) : O(O) {}
    bool operator()(Point const &A, Point const &B) {
        return SignedArea(O, A, B) > 0;  // 逆时针排序
    }
};

// 从线段出发的角度比较
struct CmpAngleFromSegment {
    Point const &P;
    Point const &Q;
    CmpAngleFromSegment(Point const &P, Point const &Q) : P(P), Q(Q) {}
    bool operator()(Point const &A, Point const &B) {
        bool sgnA = SignedArea(P, Q, A) > 0;
        bool sgnB = SignedArea(P, Q, B) > 0;
        if (sgnA != sgnB) return sgnA;
        return SignedArea(P, A, B) > 0;
    }
};

3. 核心分治算法

void DrawPath(Node *A, Node *B, Point const &pA, Point const &pB, Point *p, int n) {
    Node *C = GetMidPoint(A, B);  // 找到路径中点
    
    if (C == B) return;
    
    // 计算重链和轻链的大小
    int heavy_size = Size(C->Heavy()) - Size(B);
    int light_size = Size(C->Light());
    
    // 为中间节点C选择点
    nth_element(p, p + heavy_size, p + n, cmpB);
    nth_element(p, p + heavy_size + light_size, p + n, cmpA);
    
    // 选择满足几何约束的点
    Point &pC = p[0];
    pC.vertex = C->index;
    
    // 递归处理三个部分
    CmpAngleFromSegment cmpC(pC, pB);
    nth_element(p + 1, p + 1 + heavy_size, p + n, cmpC);
    DrawPath(C, B, pC, pB, p + 1, heavy_size);  // 重链部分
    
    nth_element(p + 1 + heavy_size, p + 1 + heavy_size + light_size, p + n, cmpC);
    DrawPath(C, DiveHeavy(C->Light()), pC, p + 1 + heavy_size, light_size);  // 轻链部分
    
    DrawPath(A, C, pA, pC, p + 1 + heavy_size + light_size, n - 1 - heavy_size - light_size);  // 剩余部分
}

算法正确性

为什么能保证线段不相交？

1. 凸包性质：每次选择点都基于凸包或半平面约束
2. 分离定理：通过有向面积确保点在不同半平面
3. 树结构利用：重链分解确保几何约束的一致性

关键几何引理

对于任意三点 $A, B, C$，有向面积 $S(ABC)$ 的正负决定了 $C$ 在直线 $AB$ 的哪一侧：

• $S(ABC) > 0$：$C$ 在 $AB$ 左侧（逆时针）
• $S(ABC) < 0$：$C$ 在 $AB$ 右侧（顺时针）

复杂度分析

• 树构建：$O(n)$
• 每次分治：$O(n \log n)$ 的几何排序
• 总复杂度：$O(n \log^2 n)$

样例验证

样例1：三角形

• 3个点形成三角形
• 链状树 $1-2-3$
• 按凸包顺序分配编号

样例2：星形树

• 中心节点连接4个叶子
• 通过分治确保各分支在不同区域

样例3：复杂树结构

• 验证算法对复杂树结构的适应性

关键技巧

1. 重链分解：利用树的重轻链结构指导点分配
2. 几何排序：使用有向面积进行快速排序和选择
3. 分治策略：将问题分解为更小的子问题
4. 凸包利用：始终保持点在合适的凸包区域内

总结

本题的巧妙之处在于：

1. 问题转化：将图嵌入问题转化为几何分治问题
2. 数据结构结合：树的重链分解与几何算法的结合
3. 高效实现：利用nth_element进行线性时间选择
4. 正确性保证：通过严格的几何约束确保无交叉

这种"树分解 + 几何分治"的方法为解决平面嵌入问题提供了有效的范例。