CF765E Tree Folding
题目链接
题意
给出一颗无根树，你可以钦定一个根，并进行若干次下述操作：
- 选择一个点 \(v\)，以及 \(v\) 延伸出去的两条长度相同的路径（两条路径没有重叠的边）。删去其中任意一条（不删 \(v\)）。
现在，操作次数、\(v\) 以及两条路径都由你决定，但你需要求出，是否可以把这颗无根树删成一条链；假若能，最短的链长是多少。
解题思路
任取一个根，进行一遍 \(\text{DFS}\)，同时计算每颗子树是否可以合并成一条链/链的长度。
但问题在于如何把节点 \(u\) 的所有儿子子树的信息合并为整颗子树的信息。先特判掉部分不合法的情况——有至少一颗子树返回不合法状态。之后考虑在 \(u\) 的位置维护一个链长可重集，合并某颗儿子的子树时就直接把链长加进可重集里。
合并完后，我们进行一个分类讨论：
-
有 \(0\) 种不同的链长
证明这个节点是叶节点，返回 \(0\)。
-
只有 \(1\) 种链长（设它为 \(l\)）
子树合并后的链长为 \(l\)。
-
有两种不同的链长
-
当前节点不是根节点
会发现在当前的树最后不可能变成一条链，同时记录一个 \(rt2\)，\(rt2=u\)。
-
当前节点为根节点
形成了一条链，返回两种链长相加。
-
-
有 \(>2\) 种不同的链长
最终不可能变成一条链。
这样的策略是在钦定了一个根的情况下。假设通过上述流程，最终没法变成一条链，考虑把 \(rt2\) 提为根再做一遍。这样便可保证答案正确（假设 \(rt2\) 为根还不行，归纳一下便可得这棵树确实不合法）。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 2e5 + 10;
unordered_map<int, int> mp[N];
int n, r, ans, rt = 1;
vector<int> e[N];
int dfs(int u, int p){
unordered_map<int, int>().swap(mp[u]);
for(int &v: e[u]) if(v != p){
mp[u][r = dfs(v, u) + 1] = 1;
if(!r) return -1;
}
if(!mp[u].size()) return 0;
if(mp[u].size() <= 1 + (!p)){
r = 0; for(auto &it: mp[u]) r += it.first;
return r;
}
rt = u; return -1;
}
int main(){
scanf("%d", &n);
FL(i, 2, n){
int u, v; scanf("%d%d", &u, &v);
e[u].emplace_back(v), e[v].emplace_back(u);
}
dfs(1, 0), ans = dfs(rt, 0);
printf("%d\n", ans >> __builtin_ctz(ans));
return 0;
}