记录编号	609759	评测结果	AAAAAAAAAA
题目名称	路径覆盖	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	0.409 s
提交时间	2025-11-25 19:26:01	内存使用	14.25 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
vector<int>G[N];
int n,q;
struct mat{
	int x[3][3],n,m;
	void reset(int r,int c){
		n=r,m=c;
		memset(x,0x3f,sizeof(x));
	}
	void print(){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				printf("%d ",x[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		return;
	}
}c,val[N],f[N],I,g[N],P;
vector<mat>suf,pre;
mat operator * (const mat &a,const mat &b){
	c.reset(a.n,b.m);
	for(int i=0;i<a.n;i++){
		for(int j=0;j<b.m;j++){
			for(int k=0;k<a.m;k++){
				c.x[i][j]=min(c.x[i][j],a.x[i][k]+b.x[k][j]);
			}
		}
	}
	return c;
}
mat getm(mat v){
	mat va;va.reset(3,3);
	va.x[0][0]=v.x[0][2];
	va.x[0][1]=min(v.x[0][1],v.x[0][0]+1);
	va.x[0][2]=inf;
	va.x[1][0]=min(v.x[0][0],v.x[0][1]-1);
	va.x[1][1]=v.x[0][2];
	va.x[1][2]=inf;
	va.x[2][0]=inf;
	va.x[2][1]=inf;
	va.x[2][2]=min(v.x[0][0],v.x[0][1]); 
	return va;
}
void add(int x,int y){
	G[x].push_back(y);
}
void dfs1(int x,int fa){
	f[x]=g[x]=P;
	for(auto y:G[x]){
		if(y==fa)continue;
		dfs1(y,x);
		f[x]=(f[x]*val[y]);
	}
	val[x]=getm(f[x]);
	return;
}
void dfs2(int x,int fa){
	int L=G[x].size()-1;
	suf.clear();pre.clear();
	for(int i=0;i<=L;i++){
		if(G[x][i]==fa){
			suf.push_back(I);
			pre.push_back(I);
		}else{
			suf.push_back(val[G[x][i]]);
			pre.push_back(val[G[x][i]]);
		} 
	}
	for(int i=1;i<=L;i++)suf[i]=(suf[i-1]*suf[i]);
	for(int i=L-1;i>=0;i--)pre[i]=(pre[i]*pre[i+1]); 
	for(int i=0;i<=L;i++){
		if(G[x][i]==fa)continue;
		int y=G[x][i];mat w=I;
		if(i!=0)w=(w*suf[i-1]);
		if(i!=L)w=(w*pre[i+1]);
		if(x!=1)g[y]=P*w*getm(g[x]);
		else g[y]=P*w;
	}
	for(auto y:G[x]){
		if(y==fa)continue;
		dfs2(y,x);
	}
	return;
}
int main(){
	freopen("lucover.in","r",stdin);
	freopen("lucover.out","w",stdout);
	I.reset(3,3);
	I.x[0][0]=0,I.x[1][1]=0,I.x[2][2]=0;
	P.reset(1,3);
	P.x[0][0]=0,P.x[0][1]=inf,P.x[0][2]=1;
	scanf("%d %d",&n,&q);
	for(int i=1,u,v;i<n;i++){
		scanf("%d %d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)f[i]=(f[i]*getm(g[i]));
	for(int i=1,x;i<=q;i++){
		scanf("%d",&x);
		printf("%d\n",f[x].x[0][2]);
	}
	return 0;
}