[??记录]AT3734 [ARC088D] Christmas Tree

**题意** ： 给定一棵 $N$ 个节点的树。用如下方法生成一棵与其相同的树： - 首先生成 $A$ 个点数均不超过 $B$ 的链。 - 重复以下操作直到所有的点连通： - 选择两个当前属于不同连通块的点，将这两个点**合并为一个点**，所有原来与这两个点中的至少一个点有边的点与这个新点有边。 - 将点重新标号。 求出能够生成给定树的最小的 $A$ 值，在最小化 $A$ 的基础上最小化 $B$ 值。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 我们发现，操作相当于把两个点“重叠”。 问题相当于将若干条链重合在树上，使得每条边都被链覆盖至少一次。 由于重叠的点之前必须不连通，则任意两条链必须至多有一个点相交，即边不相交。不难发现这同时也是充分条件。 先求 $A$ ，考虑 $\rm DP$。 即 $dp_u$ 为覆盖 $u$ 子树所需的链条数目，并且儿子向父亲连出一条链。 在 $u$ 处，若有 $c_u$ 个直接儿子，则尽量将儿子两两配对，配成 $\lfloor c_u/2\rfloor$ 个对子。 若 $c_u$ 是奇数，则刚好剩下一条链向上延伸，否则还要新建一条链。 接下来求 $B$ ，显然，$B$ 越大则所需的 $A$ 越小，于是考虑二分答案，跑一个类似 [P5021 [NOIP2018 提高组] 赛道修建](https://www.luogu.com.cn/problem/P5021) 的贪心即可。 复杂度为 $O(n\log^2n)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<set> #define pb push_back #define MaxN 100500 using namespace std; vector<int> g[MaxN]; int f[MaxN],lim,cnt; multiset<int> s; void dfs(int u,int fa) { for (int i=0,v;i<g[u].size();i++) if (g[u][i]!=fa)dfs(g[u][i],u); s.clear(); for (int i=0,v;i<g[u].size();i++) if (g[u][i]!=fa&&f[g[u][i]]>1) s.insert(f[g[u][i]]-1); int up=0; while(s.size()>1){ multiset<int>::iterator it,it2; it=s.begin(); int x=*it;s.erase(it); it2=s.lower_bound(lim-x); if (it2!=s.end()){cnt--;s.erase(it2);} else up=max(up,x); } if (!s.empty())up=max(up,*s.rbegin()); if (fa&&!up){f[u]=lim;cnt++;} else f[u]=up; } int n,A; bool chk() {cnt=0;dfs(1,0);return cnt==A;} 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); } lim=n-1;chk();A=cnt; int l=1,r=n-1; while(l<r){ lim=(l+r)>>1; if (chk())r=lim; else l=lim+1; }printf("%d %d\n",A,r); return 0; } ```