求条,玄关()
查看原帖
求条,玄关()
1287433
__ycy1124__楼主2025/7/19 11:36
#include<bits/stdc++.h>
#define N 600005
#define int long long
using namespace std;
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	register int x=0;
	register char ch=getchar();
	while(!(ch>='0'&&ch<='9'))
		ch=getchar();
	while(ch>='0'&&ch<='9')
		x=x*10+(ch^48),ch=getchar();
	return x;
}
inline void write(register int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
    (x>9)?write(x/10):void();
    putchar((x%10)^48);
}
struct Flush{
    ~Flush(){flush();}
}_;
vector<int>a[N],b[N];
int n,m,rot,md,idx,qwq[N],dfn[N],siz[N],dep[N],fa[N],son[N],top[N],book[N],h[N],dp[N],len,color[N],qaq[N];
bool bj[N];
void dfs1(int p,int w){
	dep[p]=w;
	int ma=0;
	siz[p]=1;
	for(auto it:a[p]){
		if(siz[it]){
			continue;
		}
		fa[it]=p;
		dfs1(it,w+1);
		siz[p]+=siz[it];
		if(siz[ma]<siz[it]){
			ma=it;
		}
	}
	son[p]=ma;
}
void dfs2(int p){
	if(p==0){
		return;
	}
	dfn[p]=++idx;
	qwq[p]=dfn[p];
	book[idx]=p;
	if(son[fa[p]]==p){
		top[p]=top[fa[p]];	
	}
	else{
		top[p]=p;
	}
	dfs2(son[p]);
	if(son[p]){
		qwq[p]=qwq[son[p]];
	}
	for(auto it:a[p]){
		if(dfn[it]){
			continue;
		}
		dfs2(it);
	}
	qwq[p]=idx;
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
bool cmp(int u,int v){
	return dfn[u]<dfn[v];
}
void add(int u,int v){
	b[u].push_back(v);
	b[v].push_back(u);	
}
int dfs3(int p,int w){
//	cout<<"3 "<<p<<' '<<'\n';
	if(bj[p]){
		color[p]=p;
		qaq[p]=0;
		for(auto it:b[p]){
			if(dep[it]<dep[p]){
				continue;
			}
			dfs3(it,0-dep[p]+dep[it]);
		}
	}
	else{
		for(auto it:b[p]){
			if(dep[it]<dep[p]){
				continue;
			}
			int x=dfs3(it,w-dep[p]+dep[it]);
			if(qaq[p]>dep[p]-dep[x]){
				qaq[p]=x;
				color[p]=x;
			}
			else if(qaq[p]==dep[p]-dep[x]){
				if(x<color[p]){
					color[p]=x;
				}
			}
		}
	}
}
void dfs4(int p,int w,int f){
//	cout<<p<<' '<<'\n';
	if(w<qaq[p]&&!bj[p]){
		color[p]=f;
		qaq[p]=w;
	}
	else{
		w=0;
		f=color[p];
	}
	for(auto it:b[p]){
		if(dep[it]<dep[p]){
			continue;
		}
		dfs4(it,w+dep[it]-dep[p],f);
	}
}
void dfs5(int p){
//	cout<<p<<' '<<'\n';
	dp[color[p]]+=siz[p];
	for(auto it:b[p]){
		if(dep[p]>dep[it]){
			continue;
		}
		dfs5(it);
		dp[color[p]]-=color[it];
		if(color[p]==color[it]){
			continue;
		}
		int x=dep[it]-dep[p]-1;
		dp[color[p]]-=x;
		if(qaq[p]-qaq[it]<0){
			dp[color[p]]+=min(qaq[it]-qaq[p],x);
			x+=qaq[p]-qaq[it];
		}
		else{
			dp[color[it]]+=min(qaq[p]-qaq[it],x);
			x+=qaq[it]-qaq[p];
		}
		if(x<=0){
			continue;
		}
		dp[color[it]]+=x/2;
		dp[color[p]]+=x/2;
		if(x%2){
			dp[min(color[p],color[it])]++;
		}
		continue;
	}
}
signed main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v);
	}
	dfs1(1,1);
	dfs2(1);
	m=read();
	for(int i=1;i<=m;i++){
		int k=read();
		len=0;
		for(int j=1;j<=k;j++){
			h[++len]=read();
			bj[h[len]]=1;
		}
		sort(h+1,h+len+1,cmp);
		for(int j=1;j<k;j++){
			h[++len]=lca(h[j],h[j+1]);
		}
		h[++len]=1;
		sort(h+1,h+len+1,cmp);
		len=unique(h+1,h+len+1)-h-1;
		for(int j=1;j<len;j++){
			add(h[j+1],lca(h[j],h[j+1]));
		}
		for(int j=1;j<=len;j++){
			qaq[h[j]]=1e9; 
		}
		dfs3(1,1e9);
		dfs4(1,1e9,0);
		dfs5(1);
		for(int j=1;j<=len;j++){
			if(bj[h[j]]){
				write(dp[h[j]]);
				putchar(' ');
			}
		}
		putchar('\n');
		for(int j=1;j<=len;j++){
			b[h[j]].clear();
			dp[h[j]]=0;
			bj[h[j]]=0;
		}
	}
	return 0;
}
/*
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8
*/
2025/7/19 11:36
加载中...