样例已过求条(玄10rmb+关)
查看原帖
样例已过求条(玄10rmb+关)
1287433
__ycy1124__楼主2025/7/19 16:56
#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],H[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){
    if(u==v){
        return;
    }
    b[u].push_back(v);
    b[v].push_back(u);    
}
int dfs3(int p){
    if(bj[p]){
        color[p]=p;
        qaq[p]=0;
    }
    for(auto it:b[p]){
        if(dep[it]<dep[p]){
            continue;
        }
        int x=dfs3(it);
        if(qaq[p]>dep[x]-dep[p]){
            qaq[p]=dep[x]-dep[p];
            color[p]=x;
        }
        else if(qaq[p]==dep[x]-dep[p]){
            if(x<color[p]){
                color[p]=x;
            }
        }
    }
    return color[p];
}
void dfs4(int p,int w,int f){
    if(w<qaq[p]&&!bj[p]){
        color[p]=f;
        qaq[p]=w;
    }
    else if(w==qaq[p]&&color[p]>color[f]){
        color[p]=f;
    }
    for(auto it:b[p]){
        if(dep[it]<dep[p]){
            continue;
        }
        dfs4(it,qaq[p]+dep[it]-dep[p],color[p]);
    }
}
void dfs5(int p){
    dp[color[p]]+=siz[p];
    for(auto it:b[p]){
        if(dep[p]>dep[it]){
            continue;
        }
        dfs5(it);
        dp[color[p]]-=siz[it];
        if(color[p]==color[it]){
            continue;
        }
        int x=dep[it]-dep[p]-1;
        if(x<=0){
            continue;
        }
        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[p]]+=x/2;
        dp[color[it]]+=x/2;
        if(x%2){
            dp[min(color[p],color[it])]++;
        }
        continue;
    }
}
signed main(){
	freopen("P3233_1.in","r",stdin);
	freopen("P3233_1.ans","w",stdout);
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        a[u].push_back(v);
        a[v].push_back(u); 
    }
    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();
            H[j]=h[len];
            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);
        dfs4(1,1e9,0);
        dfs5(1);
        for(int j=1;j<=k;j++){
            if(bj[H[j]]){
                write(dp[color[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;
}
2025/7/19 16:56
加载中...