样例过了
#include<bits/stdc++.h>
using namespace std;
int k,n,head[10005],sweet,tot,first[100005],dis[10005],cnt[10005],on[10005],node[10005],a,b,h;//dis[i]表示第i个节点离根距离,on[i]表示第i个贪吃虫当前的位置,node[i]表示第i个节点当前的贪吃虫编号(node[i]=0表示当前节点没有贪吃虫)
struct bian{
int from,to,nxt;
}e[10005];
void add(int a,int b){
e[++tot]={a,b,head[a]};
head[a]=tot;
}//链式前向星
void dfs1(int x,int fa){
if(node[x]){
first[node[x]]=dis[x];
}
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa){
dis[to]=dis[x]+1;//因为这是一棵树所以每个节点只会搜到一次,我就直接更新了
dfs1(to,x);
}
}
}
void dfs(int x,int fa,bool flag){//x表示当前dfs搜到的节点编号,fa表示上一个节点编号,避免重复搜,flag表示该路线上是否有离根更近的贪吃虫
vector<int> v;//用来记录有贪吃虫的子节点编号
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa){
dfs(to,x,flag&&(!node[x]));//如果此时node[x]不为0,则以x为根的树上的贪吃虫也不会移动
if(node[to]){
v.push_back(to);
}
}
}if(node[x]||(!flag)){//若此处有贪吃虫,它的子节点上的贪吃虫就不会移动
return ;
}int min1=2e9,minid=2e9,minnode=0;//min1表示v中dis的最小值,minid表示应该移动的贪吃虫不会,minnode表示该移动的贪吃虫所在的节点的编号
for(auto it:v){
if(first[node[it]]<min1){
min1=first[node[it]];
minnode=it;
minid=node[it];
}else if(first[node[it]]==min1&&node[it]<minid){
min1=first[node[it]];
minnode=it;
minid=node[it];
}
}if(minnode){//如果minnode=0说明子节点上没有贪吃虫,不需要做任何操作
node[x]=node[minnode];
node[minnode]=0;
on[minid]=x;//将应该移动的贪吃虫移动到x
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);//链接ab,这里应该是无向图
}scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",&on[i]);
node[on[i]]=i;//初始化
}scanf("%d",&h);
for(int i=1;i<=h;i++){
scanf("%d",&sweet);
memset(dis,0,sizeof(dis));//因为每次的根不同,所以清空了dis
memset(first,0,sizeof(first));
dis[sweet]=1;
dfs1(sweet,-1);
dfs(sweet,-1,1);
cnt[node[sweet]]++;
}for(int i=1;i<=k;i++){
printf("%d %d\n",on[i],cnt[i]);
}
}