[Luogu3233] [LOJ2206]

题解及代码

题意 : 标记一些树上的点,每个点会被最近(编号最小)的标记点控制,问每个标记点会控制多少点

先用两遍\(dfs\)求出每个点被哪个点控制 , 第一遍找儿子的贡献 , 第二遍找父亲的贡献
然后套路建虚树

然后对于虚树上每一条边 , 如果两个点被同一个点控制 , 倍增找出\(u\)到\(v\)路径上离\(u\)最近的点 \(s\), \(ans[bel[u]]+=size[s]-size[v]\)

否则一定有一个分界点 \(mid\) , 可以通过倍增求得 , \(ans[bel[u]]+=size[s]-size[mid], ans[bel[v]]+=size[mid]-size[v]\)

统计出不在虚树中的节点数量, \(sur[u]=size[u]-\sum{size[s]}\)
最后\(ans[bel[u]]+=sur[u]\)

代码实现中空间的利用也比较麻烦

具体细节见代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int N=3e5+5;
const int M=6e5+5;
const int logN=19;

struct Edge{
    int v,w,nxt;
}e[M];
int first[N],Ecnt=0;
inline void Add_edge(int u,int v,int w=0){
    e[++Ecnt]=(Edge){v,w,first[u]};
    first[u]=Ecnt;
}

int fa[N][logN],top[N],son[N],dfn[N],dep[N],log[N],sur[N],ans[N],st[N],a[N],b[N],bel[N],size[N];
bool mark[N];
int n,m,K,dft,tp;

inline void dfs1(int u,int pre){
    dfn[u]=++dft,dep[u]=dep[pre]+1,size[u]=1;
    fa[u][0]=pre;
    for(int i=1;fa[u][i-1];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==pre) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
inline void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u]) dfs2(son[u],top[u]);
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa[u][0]||v==son[u]) continue;
        dfs2(v,v);
    }
}
inline bool cmp(int a,int b){return dfn[a]<dfn[b];}

inline int LCA(int x,int y){
    for(;top[x]^top[y];dep[top[x]]>dep[top[y]]?x=fa[top[x]][0]:y=fa[top[y]][0]);
    return dep[x]<dep[y]?x:y;
}
inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}

inline void dfs3(int u){
    int d1,d2;
    bel[u]=mark[u]*u;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        dfs3(v);
        d1=dep[bel[v]]-dep[u],d2=bel[u]?dep[bel[u]]-dep[u]:INF;
        if(d1<d2||(d1==d2&&bel[v]<bel[u])) bel[u]=bel[v];
    }
}
inline void dfs4(int u){
    int d1,d2;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        d1=dis(bel[u],v),d2=dis(bel[v],v);
        if(d1<d2||(d1==d2&&bel[u]<bel[v])) bel[v]=bel[u];
        dfs4(v);
    }
}
inline void dp(int u){
    int s,mid,tmp,d1,d2;
    sur[u]=size[u];
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].v;
        dp(v);
        s=mid=v;
        for(int i=log[dep[v]];i>=0;i--){
            if(dep[fa[s][i]]>dep[u]) s=fa[s][i];    
        }
        sur[u]-=size[s];//减去在虚树中的
        if(bel[u]==bel[v]){
            ans[bel[u]]+=size[s]-size[v];//关于bl[v]会在v计算,即这里只考虑了上界
            continue;
        }
        for(int i=log[dep[v]];i>=0;i--){
            tmp=fa[mid][i];if(dep[tmp]<=dep[u]) continue;
            d1=dis(tmp,bel[v]),d2=dis(tmp,bel[u]);
            if(d1<d2||(d1==d2&&bel[v]<bel[u])) mid=tmp;
        }
        ans[bel[u]]+=size[s]-size[mid];
        ans[bel[v]]+=size[mid]-size[v];
    }
    ans[bel[u]]+=sur[u];//加上不在虚树中的
    first[u]=0;//一定要在这里就清空!!!
}

inline void solve(){
    K=read();
    for(int i=1;i<=K;i++) a[i]=read(),b[i]=a[i],mark[a[i]]=1;
    sort(a+1,a+K+1,cmp);//按dfn排序后方便操作
    st[tp=1]=1;
    Ecnt=0;
    for(int i=1;i<=K;i++){
        int x=a[i],p=LCA(st[tp],x);
        while(dep[p]<dep[st[tp]]){//建虚树套路
            if(dep[p]>=dep[st[tp-1]]){
                Add_edge(p,st[tp--]);
                if(p!=st[tp]) st[++tp]=p;//使得关键点在栈中深度递增
                break;
            }
            Add_edge(st[tp-1],st[tp]),tp--;//建边的顺序
        }
        if(st[tp]!=x) st[++tp]=x;
    }
    while(tp>1) Add_edge(st[tp-1],st[tp]),tp--;//1号点也会被加入
    dfs3(1);dfs4(1);dp(1);
    for(int i=1;i<=K;i++){
        printf("%d ",ans[b[i]]);
        mark[b[i]]=false,ans[b[i]]=0;
    }
    printf("\n");
}

int main(){
    n=read();
    for(int i=2;i<=n;i++) log[i]=log[i>>1]+1;
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        Add_edge(x,y);Add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    memset(first,0,sizeof first);//图已经没用了,有用的只是size[],dep[]等已经求出的东西
    for(int i=read();i;i--) solve();
}