1 条题解
-
0
考虑可行构造的上下界。对于一条边,如果其两侧点数均为偶数,则最小可以经过 次该边,如果两侧点数均为奇数,则最小可以经过 次该边,最大均可以经过两侧较小的点数的次数。
显然,如果不在上述范围内或者奇偶性与上述不匹配说明一定无解。下面构造其他情况的解。
首先构造出一个距离和最大的解。每个点的深度固定,为了让距离和最大,只需让每个点对的 LCA 深度最小。不妨让 LCA 均为根结点,那么每次从根结点的子树中选出两个大小最大的子树的两个点配对删除,最后剩下一个点与根结点配对即可实现最大解。注意为了防止出现一棵子树的结点数超过总点数的一半,多余结点无法配对的情况,可以选择整棵树的重心作为根结点。
考虑怎么让距离和变小。只要让一个 LCA 变深 个单位,答案就可以变小 。考虑找出一个深度最大的非叶子结点,删除它的两个儿子或者一个儿子和它自己,剩下的部分按照原方案配对即可实现答案变小 。但是答案可能会变得比目标还小,只需在这个时候让 LCA 往上跳父亲,找到一个我们需要的深度即可。
注意为了保证最后仍然不存在超过总点数一半的子树,每次调整 LCA 的时候要选择最大的那一棵子树操作。
#include<bits/stdc++.h> using namespace std; int n; long long k,now; set<int> E[100001]; bool vis[100001]; void removeEdge(int u,int v){ E[u].erase(v),E[v].erase(u); } int siz[100001],maxsiz[100001],root; void findRoot(int u,int father){ siz[u]=1; for(int v :E[u]){ if(v==father)continue; findRoot(v,u); siz[u]+=siz[v]; maxsiz[u]=max(maxsiz[u],siz[v]); } maxsiz[u]=max(maxsiz[u],n-siz[u]); if(!root||maxsiz[u]<maxsiz[root])root=u; } int dep[100001],fa[100001]; void init(int u,int father){ dep[u]=dep[father]+1; siz[u]=1,fa[u]=father; for(int v :E[u]){ if(v==father)continue; init(v,u); siz[u]+=siz[v]; } } set<pair<int,int>> lca[100001]; void listLCA(int u,int id){ int cnt=0; for(int v :E[u]){ if(v==fa[u])continue; cnt++,listLCA(v,id); } if(cnt)lca[id].insert({dep[u],u}); } vector<int> target[100001]; void listTarget(int u,int id){ if(!vis[u])target[id].push_back(u); for(int v :E[u]){ if(v==fa[u])continue; listTarget(v,id); } } int main(){ scanf("%d%lld",&n,&k); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); E[u].insert(v); E[v].insert(u); } findRoot(1,0); dep[0]=-1,init(root,0); long long minn=0,maxn=0; for(int i=1;i<=n;i++) if(i!=root)minn+=siz[i]&1,maxn+=siz[i]; if(k<minn||k>maxn||(k&1)!=(minn&1))return puts("NO"),0; puts("YES"); now=maxn; priority_queue<pair<int,int>> Q; for(int u :E[root]){ Q.push({siz[u],u}); listLCA(u,u); } while(true){ int u=Q.top().second; if(now==k)break; Q.pop(); if(siz[u]==1)break; siz[u]-=2; int x=(*lca[u].rbegin()).second; if(now-dep[x]*2>k){ now-=dep[x]*2; vector<int> match; for(int v :E[x]){ if(v!=fa[x])match.push_back(v); if(match.size()==2)break; } if(match.size()==1){ vis[x]=vis[match[0]]=true; printf("%d %d\n",x,match[0]); removeEdge(x,match[0]); removeEdge(x,fa[x]); lca[u].erase({dep[x],x}); if(E[fa[x]].size()==1)lca[u].erase({dep[fa[x]],fa[x]}); } else{ vis[match[0]]=vis[match[1]]=true; printf("%d %d\n",match[0],match[1]); removeEdge(x,match[0]); removeEdge(x,match[1]); if(E[x].size()==1)lca[u].erase({dep[x],x}); } } else{ int require=(now-k)/2,son=-1; for(int v :E[x]) if(v!=fa[x]){ son=v; break; } while(dep[x]>require)x=fa[x]; printf("%d %d\n",x,son); vis[x]=vis[son]=true,now=k; } if(siz[u])Q.push({siz[u],u}); } for(int u :E[root])listTarget(u,u); while(Q.size()>=2){ int x=Q.top().second; Q.pop(); int y=Q.top().second; Q.pop(); int u=target[x].back(),v=target[y].back(); printf("%d %d\n",u,v); target[x].pop_back(),target[y].pop_back(); siz[x]--,siz[y]--; if(siz[x])Q.push({siz[x],x}); if(siz[y])Q.push({siz[y],y}); } printf("%d %d\n",root,target[Q.top().second].back()); return 0; }
- 1
信息
- ID
- 779
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者