[??记录]AT2293 [AGC009D] Uninity

**题意** : 定义一个单独的节点为一棵 Uninity $0$ 的树。 将若干棵 Uninity $k$ 的树全部连到一个节点上形成的树，称之为一棵 Uninity $k+1$ 的树。 一棵 Uninity $k$ 的树，同样也是一棵 Uninity $k+1,k+2,k+3\dots$ 的树。 现在给你一棵树，求一个最小的 $k$ 使得这棵树是一棵 Uninity $k$ 的树。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 不难发现问题等价于 ： 对给定树点分治的最少层数。 所以，答案有显然的上界 $O(\log n)$。 点分树的充要条件 ： 记 $dep_u$ 为 $u$ 点在点分树中的深度，则对于 $dep_u=dep_v$ 的 $u,v$ 原树上的路径 $u\leftrightarrow v$ 中必然存在一个点 $t$ 满足 $dep_t<dep_u,dep_v$。 反过来考虑，我们给每个点一个从 $1$ 开始的标号，要求原树路径中总有一个比端点更大的标号。 记 $g[i]$ 表示标号 $i$ 是否出现，不难发现在最优方案中，若 $g[i]=1$ 则所有 $j\leq i$ 的 $g[j]=1$。 在树上 $dfs$ 并贪心 ： 设 $f[u][i]$ 表示是否存在某个标号为 $i$ 的点到 $u$ 的路径上没有 $>i$ 的编号。 在决策 $u$ 的标号时，对于某个 $i$ ，若存在子树 $v$ 满足 $f[v][i]=1$ ，则 $u$ 的标号不能为 $i$。 选择一个尽量小的合法标号即可。 由于 $i\leq O(\log n)$ ，可以压位记录。 复杂度 $O(n\log n)$ 或 $O(n)$ （若使用位运算函数） ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define MaxN 100500 using namespace std; vector<int> g[MaxN]; int ans,f[MaxN]; void dfs(int u,int fa) { for (int i=0,v;i<g[u].size();i++) if ((v=g[u][i])!=fa) dfs(v,u); int o[22]; for (int k=0;k<20;k++)o[k]=0; for (int i=0,v;i<g[u].size();i++) if ((v=g[u][i])!=fa) for (int k=0;k<20;k++) if (f[v]&(1<<k))o[k]++; int fl=0; for (int k=19;k>=0;k--){ if (o[k]>=2)break; if (!o[k])fl=k; } if (fl>ans)ans=fl; f[u]|=(1<<fl); for (int k=fl+1;k<=20;k++) if (o[k])f[u]|=(1<<k); } int n; int main() { scanf("%d",&n); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); }dfs(1,0); printf("%d",ans); return 0; } ```