[??记录]CF765E Tree Folding

**题意** ： 给出一棵 $n$ 个点的无向无根树，可以进行如下操作： - 选择点 $t,u,v$ ，使得路径 $(u,t),(v,t)$ 除了节点 $t$ 没有多余的边，且满足 $dis(u,t)=dis(v,t)$。 将 $(v,t)$ （不含 $t$）删去。（也可以理解为叠合） 判断能否将树转化为一条链，并最小化这条链的长度。 $n\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ 对于一种方案，考虑其最后一次操作。 若选择的 $t$ 在链的一端，则将最后一次操作撤回，相当于将链倍长。 如此反复撤回，知道 $t$ 在链的中间。不难证明，此时链的两端必然为叶子。 我们考虑枚举每对叶子 $a,b$。考虑先将原树变为路径 $(a,b)$ ，再不断对折。 钦定 $(a,b)$ 之后，分别处理链上各个点的子树。  若子树内无法转化为一条链，无解。（转化为一条链的充要条件是所有叶子深度都相同） 可以发现，一定存在一条分界线，使得左边的子树向左倒，右边的子树向右倒。 我们取分界点（分界线旁边任取）为根，规定只能子树内合并，是等效的。确定根后的合并非常简单。 于是，算法改进为只需枚举根。 确定根后，能合成一条链的充要条件是：叶子的深度只有 $\leq 2$ 种。 ------------ 进一步简化方案。考虑直径。 当根不在直径上时，能合成一条链的必要条件有：直径在某个子树内对折了，且直径到根的路径上没有其他分支。  对于这种情况，根选在直径中点是完全等价的。因此，我们只用考虑根在直径上的情况。 我们先单独尝试一次根为直径中点（可以证明，只可能有一个）的情况。 对于根不在直径中点的情况，直径两端就构成了两种不同的叶子深度。因此可以认为最后留下的一定是一条直径。 我们令 $(a,b)$ 为任意一条直径，尝试一次即可。 复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define lbit(x) ((x)&-(x)) #define MaxN 200500 using namespace std; vector<int> g[MaxN]; int tp,f[MaxN],dep[MaxN]; void dfs(int u,int fa) { dep[u]=dep[f[u]=fa]+1; if (dep[u]>dep[tp])tp=u; for (int i=0;i<g[u].size();i++) if (g[u][i]!=fa)dfs(g[u][i],u); } int sl[MaxN],tot; void dfs2(int u,int fa) { if (g[u].size()==1)sl[++tot]=u; for (int i=0;i<g[u].size();i++) if (g[u][i]!=fa)dfs2(g[u][i],u); } bool vis[MaxN]; int n,st[MaxN],tn; 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); }dep[0]=-1;dfs(1,0);dfs(tp,0); for (int p=tp;p;p=f[p])vis[st[++tn]=p]=1; int ans=n; bool fl=0;int mode=0; for (int k=1;k<=tn;k++){ int u=st[k]; bool e=0; for (int i=0;i<g[u].size();i++)if (!vis[g[u][i]]){ tot=0; dfs2(g[u][i],u); if (!tot)continue; for (int i=2;i<=tot;i++) if (dep[sl[1]]!=dep[sl[i]])fl=1; if ((dep[sl[1]]-(tn-k)!=k-1||mode==1)&&dep[sl[1]]-(tn-k)!=tn-k)fl=1; if (dep[sl[1]]-(tn-k)!=k-1)e=1; }if (e)mode=1; } if (!fl)ans=min(ans,(tn-1)/lbit(tn-1)); if (tn&1){ int a=0,b=0;fl=0; int rt=st[(tn+1)/2];dfs(rt,0); for (int i=0;i<g[rt].size();i++){ tot=0; dfs2(g[rt][i],rt); if (!tot)continue; for (int i=2;i<=tot;i++) if (dep[sl[1]]!=dep[sl[i]])fl=1; int x=dep[sl[1]]; if (!a)a=x; else if (a!=x){ if (!b)b=x; else if (b!=x)fl=1; } }if (!fl)ans=ans=min(ans,(a+b)/lbit(a+b)); } printf("%d",ans==n ? -1 : ans); return 0; } ```