萌新刚学虚数求调
查看原帖
萌新刚学虚数求调
718667
zhaomumu1218楼主2024/5/12 21:54
#include<bits/stdc++.h>
using namespace std;
const int Maxn=300010,INF=1000000000;
int n,m,tot,k;
vector<int>vt[Maxn];
vector<int>g[Maxn];
int dfn[Maxn],fa[Maxn][50],deep[Maxn],h[Maxn],len,a[Maxn],f[Maxn],gl[Maxn],sc[Maxn],sz[Maxn];
bool flag[Maxn];
void dfs(int now){
    flag[now]=1;
    sz[now]=1;
    dfn[now]=++tot;
    for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1];
    for(int i=0;i<vt[now].size();i++)
        if(flag[vt[now][i]]==0){
            fa[vt[now][i]][0]=now;
            deep[vt[now][i]]=deep[now]+1;
            dfs(vt[now][i]);
            sz[now]+=sz[vt[now][i]];
        }
}
int lca(int a,int b){
    if(deep[a]<deep[b]) swap(a,b);
    for(int i=20;i>=0;i--)
        if(deep[fa[a][i]]>=deep[b]) a=fa[a][i];
    if(a==b) return a;
    for(int i=20;i>=0;i--)
        if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
void build(){
    sort(h+1,h+1+k,cmp);
    len=0;
    for(int i=1;i<k;i++){
        int l=lca(h[i],h[i+1]);
        a[++len]=h[i];
        a[++len]=l;
    }
    a[++len]=h[k];
    sort(a+1,a+1+len,cmp);
    len=unique(a+1,a+1+len)-a-1;
    for(int i=1;i<=len;i++) g[a[i]].clear();
    for(int i=1;i<len;i++){
        int l=lca(a[i],a[i+1]);
        g[l].push_back(a[i+1]);
    }
}
void bz(int u,int v){
	int x=v;
	for(int i=20;i>=0;i--){
		if(deep[x]<=deep[u]) continue;
		int dn=deep[v]-deep[fa[x][i]]+f[v],up=deep[fa[x][i]]-deep[u]+f[u];
		if(dn<up||dn==up&&gl[v]<gl[u]) x=fa[x][i];
	}
	sc[gl[v]]+=sz[x]-sz[v],sc[gl[u]]-=sz[x];
}
void dp(int u){
	f[u]=INF;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		dp(v);
		int cha=deep[v]-deep[u];
		if(f[v]+cha<f[u]) f[u]=f[v]+cha,gl[u]=gl[v];
		else if(f[v]+cha==f[u]) gl[u]=min(gl[u],gl[v]);
	}
	if(flag[u]) gl[u]=u,f[u]=0;
}
void ddp(int u){
	sc[gl[u]]+=sz[u];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		int cha=deep[v]-deep[u];
		if(f[u]+cha<f[v]) f[v]=f[u]+cha,gl[v]=gl[u];
		else if(f[u]+cha==f[v]) gl[v]=min(gl[u],gl[v]);
		bz(u,v);
		ddp(v);
	}
	g[u].clear();
	flag[u]=0;
}
signed main(){
    scanf("%d",&n); 
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        vt[u].push_back(v);
        vt[v].push_back(u);
    }
    deep[1]=1;
    dfs(1);
    deep[0]=0;
    fa[0][0]=0;
    scanf("%d",&m);
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=m;i++){
    	scanf("%d",&k);	
    	for(int j=1;j<=k;j++) scanf("%d",&h[j]),flag[h[j]]=1,sc[h[j]]=0;
    	h[++k]=1;
    	build();
    	dp(1);
    	ddp(1);
    	for(int j=1;j<k;j++) printf("%d ",sc[h[j]]);
    	printf("\n");
    }
    return 0;
} 
2024/5/12 21:54
加载中...