题解 CF1396E【Distance Matching】

[CF1396E Distance Matching](https://www.luogu.com.cn/problem/CF1396E)解题报告： [更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15382723.html) ## 题意 给定一个 $n$ 个点的树，求是否能让树上的点两两匹配使得匹配的点距离和为 $k$（$n$ 为偶数）。 $1\leqslant n\leqslant 10^5$。 ## 分析 和最近校内考试的一道题很像。 首先，根据经典结论，合法的 $k$ 的下界为 $mn=\sum_{i=1}^n(\text{size}_x\bmod 2)$，上界为 $mx=\sum_{i=1}^n\min\{\text{size}_x,n-\text{size}_x\}$。 具体证明可以考虑取出一个点对，然后再分治构造。 大胆猜测结论，$k$ 合法当且仅当 $mn\leqslant k\leqslant mx$ 且 $mx\equiv k\pmod 2$。 证明实际上就是构造过程： 我们取重心为根，那么容易发现 $\text{size}_x\leqslant n-\text{size}_x$ 恒成立，也就是说我们取出所有经过根的路径即可以让答案取到最小值。 由于 $\sum_{x,y} \text{dis}(x,y)=\sum_{x,y} dep_x+dep_y-2dep_{\text{lca}(x,y)}$。由于前面是常数，所以我们只要让一对匹配的点对 $x,y$ 的 $\text{lca}$ 深度增加一就可以让答案增加二。 接下来是构造过程： - 如果 $k=mx$，那么我们只需要让答案取到最大，这是经典问题，我们求出树的 dfs 序并隔 $\frac{n}{2}$ 匹配即可。 - 如果 $k<mx$，那么我们取出根节点的儿子中子树大小最大的子树 $x$，容易发现其大小一定不小于 $2$，，我们取出其中子树大小大于 $1$ 且最深的节点 $y$。 - - 如果 $2\text{dep}_y\leqslant mx-k$，那么我们可以选择两个 $\text{lca}$ 为 $y$ 的点进行匹配并删除即可，此时 $k$ 会增加 $2\text{dep}_{y}$，但并不会超过 $mx$，我们回到第一步即可。 - - 如果 $2\text{dep}_y>mx-k$，那么由于 $k\equiv mx\pmod 2$ 且深度是连续的，所以一定存在一个 $\text{dep}_z=\frac{mx-k}{2}$ 的节点 $z$，我们取出两个 $\text{lca}$ 为 $z$ 的节点即可，构造结束。 这里有一个小细节：为什么可以取出一对 $\text{lca}=y$ 的节点删除。我们发现当 $y$ 的儿子数量大于 $1$ 时可以任选两个儿子，儿子数量为 $1$ 时可以直接选择 $y$ 和那个儿子。（对 $z$ 的讨论同理，因为 $z$ 是 $y$ 的非负级祖先） （感觉上面说了一堆废话） 由于第二种情况（$k<mx$ 且 $2\text{dep}_y\leqslant mx-k$）不会让重心移动，所以我们并不需要重新寻找重心，于是我们用 $\text{set}$ 模拟上述过程即可。 时间复杂度 $O(n\log n)$。 ## 代码 感谢 [Displace_ ](https://www.luogu.com.cn/user/522373) 的 hack 数据。 ```cpp #include<stdio.h> #include<set> #include<vector> using namespace std; const int maxn=100005; int n,cen,mnsz; int sz[maxn],bel[maxn],used[maxn],dep[maxn],out[maxn],fa[maxn]; long long k,mn,mx,rst; vector<int>t,dfn,v[maxn],w[maxn]; set< pair<int,int> >sons,s[maxn]; void dfs1(int x,int last){ int mxsz=0; sz[x]=1; for(int i=0;i<v[x].size();i++) if(v[x][i]!=last) dfs1(v[x][i],x),sz[x]+=sz[v[x][i]],mxsz=max(mxsz,sz[v[x][i]]); mxsz=max(mxsz,n-sz[x]); if(mnsz>mxsz) mnsz=mxsz,cen=x; if(last) mn+=sz[x]%2,mx+=min(sz[x],n-sz[x]); } void dfs2(int x,int last,int b){ sz[x]=1,dep[x]=dep[last]+1,fa[x]=last,bel[x]=b; for(int i=0;i<v[x].size();i++) if(v[x][i]!=last) out[x]++,dfs2(v[x][i],x,b),sz[x]+=sz[v[x][i]]; if(sz[x]&&out[x]>0) s[b].insert(make_pair(dep[x],x)); } void dfs3(int x,int last){ if(used[x]==0) dfn.push_back(x); for(int i=0;i<v[x].size();i++) if(v[x][i]!=last) dfs3(v[x][i],x); } void del(int x){ used[x]=1,out[fa[x]]--; if(out[fa[x]]==0) s[bel[x]].erase(make_pair(dep[fa[x]],fa[x])); } void match(int x){ t.clear(); while(t.size()<2&&w[x].size()){ if(w[x].back()!=fa[x]&&used[w[x].back()]==0) t.push_back(w[x].back()); w[x].pop_back(); } if(used[x]==0) t.push_back(x); printf("%d %d\n",t[0],t[1]),del(t[0]),del(t[1]); } int main(){ scanf("%d%lld",&n,&k); for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x),w[x].push_back(y),w[y].push_back(x); mnsz=n+1,dfs1(1,0); if(mn>k||mx<k||(mx-k)&1){ puts("NO"); return 0; } puts("YES"); for(int i=0;i<v[cen].size();i++){ dfs2(v[cen][i],cen,v[cen][i]); if(sz[v[cen][i]]>1) sons.insert(make_pair(sz[v[cen][i]],v[cen][i])); } rst=mx-k; while(rst){ int x=sons.rbegin()->second,y=s[x].rbegin()->second; sons.erase(make_pair(sz[x],x)); if(2*dep[y]>rst){ y=s[x].lower_bound(make_pair((int)(rst/2),0))->second,rst-=2*dep[y],match(y); break; } rst-=2*dep[y],match(y),sz[x]-=2; if(sz[x]>1) sons.insert(make_pair(sz[x],x)); } dfs3(cen,0); for(int i=0;i<dfn.size()/2;i++) printf("%d %d\n",dfn[i],dfn[dfn.size()/2+i]); return 0; } ```