以后博客可能一直咕咕咕了。一些做题的思考可能会直接放在代码里而不是单独写博客，因为这样太浪费时间，只有一些比较新的题才会单独写博客
思路：对于这种构造可行解使得权值和恰好为某一值的题，一般都是先求出可以构造出来的最大和最小值，然后从某个极值按照一定方法进行连续修改
我们考虑每一条边对于答案的贡献：若边$E(u,v)$把数分成$U,V$两颗子树，则该边最大的贡献是$min(sz[U],sz[V])$，最小是$sz[U]mod2$。
$min$太难处理，所以想一种办法把$min$去掉，通过重心的性质（每一个子树的$size$小于等于$frac{n}{2}$），发现直接取重心就可以把$min$去掉了
所以就可以得到
$$minans=sum_{i=1}^{n} [i eq root]sz[i]mod2$$
$$maxans=sum_{i=1}^{n} [i eq root]sz[i]$$
然后仔细想想会发现：答案有解的充要条件是$minans leq k leq maxans$且$(maxans-k)mod2=0$
充分性：通过构造方法证明。
每次取在$size$最大的子树中选取两个$lca$深度最大的点，因为本来两个点都是向字树外连的，现在自己相连，所以$Delta =2*dep[lca]$，然后删掉那两个点
容易发现这样构造是必定可以从$maxans$变成$minans$的，因为对于$sz[u]mod2=0$的边，它底下肯定两两配对；对于$sz[u]mod2=0$，这样的贪心会使得下面只有一个点向上经过它
因为点数始终为偶数，所以从最大子树删掉两个点以后不会使得次大子树的$size$大于$frac{n}{2}$，上面求$minans,maxans$的式子始终成立
当最后一次$dep[lca]*2>rest$时，因为所有不是叶子节点的点都可以作$lca$，所以$dep$必定连续，即肯定能找到构造出刚好使得$rest=0$的方案。
剩下的点按照$max$的方案，跨子树分别连就可以了
必要性：因为$Delta =2*dep[lca]$，所以如果不是$k,maxans$不是同奇同偶，一定无解
代码：
#include<bits/stdc++.h> using namespace std; const int N=120000; typedef long long ll; typedef pair<int,int> pii; #define mk make_pair int n; ll k; vector<int> v[N]; int sz[N],dep[N],fa[N],root; ll minn=N,maxn=0; void dfs1(int u,int f) { sz[u]=1; int maxsz=0; for(int i=0;i<(int)v[u].size();i++) { int to=v[u][i]; if(to==f) continue; dfs1(to,u); sz[u]+=sz[to]; maxsz=max(maxsz,sz[to]); } if(minn>max(maxsz,n-sz[u])) minn=max(maxsz,n-sz[u]),root=u; } int top[N],deg[N]; set<pii> S[N],R;//S维护子树中所有可能作为lca的点(即不是叶子) void dfs(int u,int from) { sz[u]=1; top[u]=from; if(from&&(int)v[u].size()-1>=1) S[from].insert(mk(dep[u],u)); for(int i=0;i<(int)v[u].size();i++) { int to=v[u][i]; if(to==fa[u]) continue; if(u==root) from=to; deg[u]++; dep[to]=dep[u]+1; fa[to]=u; dfs(to,from); sz[u]+=sz[to]; } } void del(int x) { if(!--deg[fa[x]]) S[top[x]].erase(mk(dep[fa[x]],fa[x])); } int vis[N]; vector<int> rem; void dfs3(int u) { if(!vis[u]) rem.push_back(u); for(int i=0;i<(int)v[u].size();i++) { int to=v[u][i]; if(to==fa[u]) continue; dfs3(to); } } int main() { scanf("%d%lld",&n,&k); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs1(1,-1); dep[root]=0; dfs(root,0); minn=0,maxn=0; for(int i=1;i<=n;i++) if(i!=root) maxn+=sz[i], minn+=sz[i]%2; if(k>maxn||k<minn||(maxn-k)&1) {puts("NO"); return 0;} puts("YES"); for(int i=0;i<v[root].size();i++) { int to=v[root][i]; if(sz[to]>1) R.insert(mk(sz[to],to)); } ll rest=maxn-k; while(rest) { int now=R.rbegin()->second; R.erase(--R.end()); int pos=S[now].rbegin()->second; if(2*dep[pos]>rest) { rest/=2; pos=S[now].lower_bound(mk(rest,0))->second; vector<int> V; V.clear(); for(int i=0;i<(int)v[pos].size();i++) { int to=v[pos][i]; if(to==fa[pos]||vis[to]) continue; V.push_back(to); } if((int)V.size()<2) V.push_back(pos); printf("%d %d ",V[0],V[1]); vis[V[0]]=1; vis[V[1]]=1; rest-=dep[pos]; break; } else { vector<int> V; V.clear(); for(int i=0;i<(int)v[pos].size();i++) { int to=v[pos][i]; if(to==fa[pos]||vis[to]) continue; V.push_back(to); } if((int)V.size()<2) V.push_back(pos); rest-=dep[pos]*2; printf("%d %d ",V[0],V[1]); vis[V[0]]=1; vis[V[1]]=1; del(V[0]); del(V[1]); } sz[now]-=2; if(sz[now]>1) R.insert(mk(sz[now],now)); } dfs3(root); int T=(int)rem.size()/2; for(int i=0;i<T;i++) printf("%d %d ",rem[i],rem[i+T]); return 0; }