問題描述
給定一棵樹 (N≤1e5)，判斷能否將頂點映射到兩行無限網格點上，使邊只在端點相交 (平面繪製)。輸出 Yes/No。
核心結構特徵：鏈、Y 型、主幹
可繪製的樹必須可分解為：
- 主幹：一條路徑 (或單點)。
- 主幹節點最多掛兩條**非鏈分支** (即度數≥3 的子樹根)。
- 其他分支必須是**鏈** (路徑)，可沿網格行展開。
不可繪製特徵：存在節點掛 ≥3 個非鏈分支，或主幹分支過於複雜。
判斷算法
- 標記鏈：從所有葉子 (度=1) 開始 DFS，沿度≤2 的路徑標記
is_leaf_chain[u]=true。這些是可直線繪製的「腿」。
- 統計非鏈分支：對每個節點
u，計算其鄰居中 非鏈**且**非父節點**的子樹數** cnt。
- Y 型節點處理：度=3 且三個鄰居中兩個是鏈、一個非鏈的節點屬於「Y 型」，可作為主幹彎曲點，允許存在。
關鍵代碼邏輯 (C++)
vector G[MAXN];
int deg[MAXN];
bool is_chain[MAXN];
void dfs_mark_chain(int u, int fa) {
is_chain[u] = true;
for (int v : G[u]) if (v != fa && deg[v] <= 2)
dfs_mark_chain(v, u);
}
int main() {
int n; scanf("%d", &n);
for (int i=1;i= 2) // 粗略：非鏈且非葉
cnt++;
}
if (cnt >= 3) { ok = false; break; }
}
puts(ok ? "Yes" : "No");
return 0;
}
複雜度分析
- 時間：O(N) — 兩次 DFS/BFS 遍歷樹。
- 空間：O(N)。
關鍵洞見
- 鏈 = 可拉直的腿：度≤2 的路徑可無交叉鋪開。
- 主幹分叉 ≤ 2：雙行網格只有「上下」兩個方向延伸主幹，第三個方向會導致交叉。
- 構造性證明：滿足條件的樹總能構造繪製方案 (主幹鋪在兩行交替，鏈腿向外延伸)。
總結
CF 574E 是一道「樹的平面繪製可行性」構造性判斷題。核心在於識別「鏈」與「非鏈分支」，並限制非鏈分支數 ≤ 2。此類「幾何約束下的圖嵌入」問題常通過提取圖的骨架結構 (主幹、腿、葉) 轉化為組合條件判斷。
