未过样例但70pts,WA on #5#6#7 求条
查看原帖
未过样例但70pts,WA on #5#6#7 求条
1067449
Chillturtle楼主2024/12/21 11:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace P3233{
    const int N=3e5+10;
    const int inf=1e9;
    int n,m,tot,M,rt=1,head[N],to[N<<1],nxt[N<<1],dfn[N],Ft[N],Stack[N],fa[N][30],Top,Dep[N],Siz[N],ans[N],a[N],b[N],cnt,Sze[N],Log[N];
    pair<int,int> Q[N];
    void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}
    bool cmp(int a,int b){return dfn[a]<dfn[b];}
    int GetLca(int u,int v){
        if(Dep[u]<Dep[v]) swap(u,v);
        for(int k=Log[Dep[u]];~k;k--) if(Dep[fa[u][k]]>=Dep[v]) u=fa[u][k];
        if(u==v) return u;
        for(int k=Log[Dep[u]];~k;k--) if(fa[u][k]!=fa[v][k]) u=fa[u][k],v=fa[v][k];
        return fa[u][0];
    }
    int Getdist(int u,int v){return Dep[u]+Dep[v]-2*Dep[GetLca(u,v)];}
    void dfs(int u){
        Sze[u]=1;dfn[u]=++cnt;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(Sze[v]) continue;
            fa[v][0]=u;Dep[v]=Dep[u]+1;
            for(int j=1;j<=Log[Dep[v]];j++) fa[v][j]=fa[fa[v][j-1]][j-1];
            dfs(v);Sze[u]+=Sze[v];
        }
        return;
    }
    void Build(int u){
        if(Top<=1){Stack[++Top]=u;return;}
        int lca=GetLca(Stack[Top],u);
        if(lca==Stack[Top]){Stack[++Top]=u;return;}
        while(Top>1&&dfn[Stack[Top-1]]>=dfn[lca]) add(Stack[Top-1],Stack[Top]),Top--;
        if(lca!=Stack[Top]) add(lca,Stack[Top]),Stack[Top]=lca;
        Stack[++Top]=u;
    }
    void dfs1(int u){
        if(Ft[u]==m) Q[u]=pair<int,int>(0,u);
        else Q[u]=pair<int,int>(1e9,0);Siz[u]=Sze[u]-1;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            dfs1(v);
            Q[u]=min(Q[u],pair<int,int>(Q[v].first+Dep[v]-Dep[u],Q[v].second));
        }
    }
    void dfs2(int u,int fa){
        if(u!=1) Q[u]=min(Q[u],pair<int,int>(Q[fa].first+Dep[u]-Dep[fa],Q[fa].second));
        ans[Q[u].second]++;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];dfs2(v,u);
        }
    }
    void dfs3(int u){
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            dfs3(v);int son=v,mid=v;
            for(int j=Log[Dep[son]];~j;j--) if(Dep[fa[son][j]]>Dep[u]) son=fa[son][j];
            Siz[u]-=Sze[son];
            if(Q[u].second==Q[v].second){ans[Q[u].second]+=Sze[son]-Sze[v];continue;}
            for(int j=Log[Dep[mid]];~j;j--){
                if(Dep[fa[mid][j]]<=Dep[u]) continue;
                if(pair<int,int>(Getdist(fa[mid][j],Q[v].second),Q[v].second)<pair<int,int>(Getdist(fa[mid][j],Q[u].second),Q[u].second)) mid=fa[mid][j];
            }
            ans[Q[u].second]+=Sze[son]-Sze[mid];
            ans[Q[v].second]+=Sze[mid]-Sze[v];
        }
        ans[Q[u].second]+=Siz[u];
        head[u]=0;
    }
    void init(){for(int i=2;i<=n;i++) Log[i]=Log[i-1]+((1<<(Log[i-1]+1))==i);}
    void inii(){tot=0;memset(head,0,sizeof head);}
    void solve(int q=0){
        cin>>q;tot=0;
        for(int i=1;i<=q;i++) cin>>a[i],b[i]=a[i],ans[a[i]]=0,Ft[a[i]]=m;
        sort(a+1,a+1+q,cmp);Top=0;
        if(Ft[1]!=m) Stack[++Top]=1;
        for(int i=1;i<=q;i++) Build(a[i]);
        while(Top>1){
            add(Stack[Top-1],Stack[Top]),Top--;
        }
        dfs1(1);dfs2(1,0);dfs3(1);
        for(int i=1;i<=q;i++) cout<<ans[b[i]]<<" ";cout<<endl;
        cout<<endl;
    }
    int main(){
        cin>>n;init();
        for(int i=1;i<n;i++){
            int u,v;cin>>u>>v;
            add(u,v);add(v,u);
        }
        Dep[1]=1;dfs(1);inii();
        cin>>m;
        while(m--) solve();
        return 0;
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    P3233::main();
    return 0;
}

2024/12/21 11:37
加载中...