出题人题解。
Analysis
首先在一棵树上，一个直径受限的点集，必定在某个中心的半径内。
记 ， 为树上 两点的距离。
- 当 为偶数时（），中心是树上的一个节点，记作 ，中心区域 ；
- 当 为奇数时（），中心是树上的一条边，记作 ，中心区域 。
任何一个合法的状态， 个被标记的点一定被至少一个合法的中心区域完整包含，所以在树上移动标记相当于中心区域的移动。
假如我们要把当前状态从中心区域 转换到 ，过程中不能违反条件，唯一的方法是先把 个标记都放在两个中心区域 的交集部分。都在交集时，所有被标记的节点都同时在两个中心区域中，因此完成了从 到 的转移。
Conclusion
两个相邻的中心区域 可以互相转移的充要条件是 。下面考虑证明。
Proof
必要性
我们把区域 划分成三个部分：， 和 。 中的任意一个节点与 中的任意一个节点之间的距离必定大于 。
这意味着，在任何合法状态下，不可能同时有标记点存在于 和 中。
所以起初点在 和 中时，如果要让任何一个点进入 ， 中不能有任何标记点。
因此 必须 才能装下这 个点。
充分性
已知 ，所以在 内部一定可以把所有节点推到 里面，所有操作都在 内进行，不会违反条件。所有点都到 之后，就都在 的范围内了，所以 的时候一定可以转移。
Construction
我们把所有中心区域看作一张图的顶点，如果两个中心区域的交集大小 就在它们之间连边。我们把得到的图称为中心图。
然后我们在中心图上搜索，如果起点和终点不连通一定无解，否则一定有解（见上证明），可获得约 。
我们记这个中心区域的移动路径为 。
（阶段 1）对于 ，我们要把所有标记放到两个区域的交集中，我们使用以下构造方式：
- 把当前 视作一棵子树；
- 不断找这棵子树的叶子节点，如果叶子节点没有标记，直接从子树中删除，否则找到距离它最近的空节点推过去。
- 处理完该叶子节点后从子树中删除，并更新子树形态。
- 重复此过程，直到当前子树完全包含于 。
（阶段 2）最后所有标记节点都在 里面的时候，还要调整到最终答案 ，我们使用以下构造方式：
- 把当前 视作一棵子树；
- 不断找这棵子树的叶子节点 ，如果叶子节点标记情况与 相同，直接从子树中删除。否则：
- 如果 有标记，目标没有，把 移到最近的空节点。
- 如果 没有标记，目标有，就把最近的有标记节点移到 的当前位置。
- 重复此过程，直到标记节点集合 。
Number of Operations
我们把中心区域路径展开成一条在树上不重复经过中心的简单路径。记所有过程中出现过的点集并为 。显然 是原树的一棵连通子树，且 。
对于 中的一条边 ，删去它后得到两个连通块，任选其中一个记为 。
在上述构造中，一旦某个连通块与当前维护的子树断开，它之后就不会再被使用。因此同一条边上的标记移动方向不会反复改变。于是经过边 的标记数量，等于初始和最终在 中的标记数量差的绝对值，即 。
又因为 大小相同，所以这个值不超过两侧点数的较小值，即 。
因此总操作次数最多为 ，其中 为 的边集。
取 的一个重心作为根。根据重心的性质，每个儿子子树大小都不超过 。对于一条父亲到儿子的边，它对上式的贡献正好等于儿子子树大小。因此上式等于所有节点到重心的距离之和。
设重心的若干个儿子子树大小为 ，则 。
对于一棵大小为 的儿子子树，它内部节点到重心的距离之和在退化成一条链取到最大值：。
又 ，因此：
由于 ，所以操作次数 。
Code
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
TP x=0;
int f=0;
char ch=getchar();
while(ch<48||ch>57) f|=ch=='-',ch=getchar();
while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
(read(args),...);
}
template<typename TP> inline void write(TP x)
{
(x<0)?(putchar('-'),x=-x):0;
(x>9)?(write(x/10),0):0;
putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
write<TP>(x);
puts("");
}
signed main()
{
int n,k,d; read(n,k,d);
vector<pair<int,int>> e(n-1);
vector<vector<int>> g(n+1);
for(auto &[u,v]:e) read(u,v),g[u].push_back(v),g[v].push_back(u);
vector<int> S(k),T(k);
for(auto &x:S) read(x);
for(auto &x:T) read(x);
vector dis(n+1,vector<int>(n+1,1e18));
rep(i,1,n)
{
queue<int> q; q.push(i),dis[i][i]=0;
while(!q.empty())
{
int u=q.front(); q.pop();
for(auto v:g[u]) if(dis[i][v]>dis[i][u]+1) dis[i][v]=dis[i][u]+1,q.push(v);
}
}
int rad=d/2,cnt=d&1?n-1:n;
vector cen(cnt,vector<int>()); vector in(cnt,vector<bool>(n+1));
rep(i,0,cnt-1)
{
if(d&1)
{
auto [u,v]=e[i];
rep(x,1,n) if(min(dis[u][x],dis[v][x])<=rad) cen[i].push_back(x),in[i][x]=1;
}
else rep(x,1,n) if(dis[i+1][x]<=rad) cen[i].push_back(x),in[i][x]=1;
}
vector cg(cnt,vector<int>());
if(d&1)
{
vector<bool> ok(n+1);
rep(v,1,n) ok[v]=count_if(dis[v].begin()+1,dis[v].end(),[&](int x){return x<=rad;})>=k;
rep(i,0,n-2) rep(j,i+1,n-2)
{
auto [u1,v1]=e[i]; auto [u2,v2]=e[j];
if((u1==u2&&ok[u1])||(u1==v2&&ok[u1])||(v1==u2&&ok[v1])||(v1==v2&&ok[v1])) cg[i].push_back(j),cg[j].push_back(i);
}
}
else rep(i,0,n-2)
{
auto [u,v]=e[i];
int cntt=0; rep(x,1,n) cntt+=in[u-1][x]&&in[v-1][x];
if(cntt>=k) cg[u-1].push_back(v-1),cg[v-1].push_back(u-1);
}
vector<int> st,ed;
rep(i,0,cnt-1)
{
int oks=1,okt=1;
for(auto s:S) oks&=in[i][s];
for(auto t:T) okt&=in[i][t];
if(oks) st.push_back(i);
if(okt) ed.push_back(i);
}
queue<int> cq; vector<int> cdis(cnt,1e18),fa(cnt,-1);
for(auto s:st) cq.push(s),cdis[s]=0;
int edok=-1;
while(!cq.empty())
{
int u=cq.front(); cq.pop();
if(find(ed.begin(),ed.end(),u)!=ed.end()) {edok=u;break;}
for(auto v:cg[u]) if(cdis[v]>cdis[u]+1) cdis[v]=cdis[u]+1,fa[v]=u,cq.push(v);
}
if(!~edok) return puts("No"),0;
vector<int> cpath; for(int x=edok;~x;x=fa[x]) cpath.push_back(x);
reverse(cpath.begin(),cpath.end());
vector<int> have(n+1),inc(n+1);
for(auto s:S) have[s]=1;
for(auto x:cen[cpath[0]]) inc[x]=1;
vector<pair<int,int>> ans;
rep(i,0,(int)cpath.size()-2)
{
int c1=cpath[i],c2=cpath[i+1];
vector<bool> ink(n+1);
rep(x,1,n) ink[x]=in[c1][x]&&in[c2][x];
vector<int> deg(n+1);
queue<int> qq;
rep(x,1,n) if(inc[x])
{
for(auto y:g[x]) deg[x]+=inc[y];
if(deg[x]<=1) qq.push(x);
}
while(!qq.empty())
{
int x=qq.front(); qq.pop();
if(!inc[x]||ink[x]) continue;
if(have[x])
{
int tar=-1; queue<int> q_; vector<int> dis_(n+1,1e18),pre(n+1,-1);
q_.push(x),dis_[x]=0;
while(!q_.empty())
{
int u=q_.front(); q_.pop();
if(!have[u]) {tar=u;break;}
for(auto v:g[u]) if(inc[v]&&dis_[v]>dis_[u]+1) dis_[v]=dis_[u]+1,pre[v]=u,q_.push(v);
}
vector<int> path; for(int u=tar;~u;u=pre[u]) path.push_back(u);
reverse(path.begin(),path.end());
req(j,(int)path.size()-2,0)
{
ans.emplace_back(path[j],path[j+1]);
have[path[j]]=0,have[path[j+1]]=1;
}
}
inc[x]=0;
for(auto y:g[x]) if(inc[y]&&(--deg[y])==1) qq.push(y);
}
for(auto x:cen[c2]) inc[x]=1;
}
vector<bool> tar(n+1); for(auto t:T) tar[t]=1;
vector<int> deg(n+1); queue<int> qq;
rep(x,1,n) if(inc[x])
{
for(auto y:g[x]) deg[x]+=inc[y];
if(deg[x]<=1) qq.push(x);
}
while(!qq.empty())
{
int x=qq.front(); qq.pop();
if(!inc[x]) continue;
if(tar[x]==have[x]) inc[x]=0;
else
{
bool noneed=have[x]&&!tar[x]; int tary=-1;
queue<int> q_; vector<int> dis_(n+1,1e18),pre(n+1,-1);
q_.push(x),dis_[x]=0;
while(!q_.empty())
{
int u=q_.front(); q_.pop();
if((noneed&&!have[u])||(!noneed&&have[u])) {tary=u;break;}
for(auto v:g[u]) if(inc[v]&&dis_[v]>dis_[u]+1) dis_[v]=dis_[u]+1,pre[v]=u,q_.push(v);
}
vector<int> path; for(int u=tary;~u;u=pre[u]) path.push_back(u);
reverse(path.begin(),path.end());
if(noneed) req(j,(int)path.size()-2,0)
{
ans.emplace_back(path[j],path[j+1]);
have[path[j]]=0,have[path[j+1]]=1;
}
else req(j,(int)path.size()-1,1)
{
ans.emplace_back(path[j],path[j-1]);
have[path[j]]=0,have[path[j-1]]=1;
}
inc[x]=0;
}
for(auto y:g[x]) if(inc[y]&&(--deg[y])==1) qq.push(y);
}
puts("Yes");
writeln(ans.size());
for(auto [u,v]:ans) write(u),putchar(32),writeln(v);
return 0;
}
暂无评论