【3】题解：P3233 [HNOI2014] 世界树【动态规划】【神人】【虚树】

· · 题解

非常有质量的神仙虚树题。

点击图片打开题目。

题意简述：给你 q 次查询，每一个点去最近的一个议会点，求之后每一个议会点来了多少个点。

考虑分类讨论：

  1. 虚树上点的归属：
    • 分给自己。
    • 分给父亲。
    • 分给儿子。
  2. 其他点的归属：
    • 只有一个固定归属点的。
    • 在两个虚树点之间被抢来抢去的。

靠多个 dfs 解决。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,INF=1e9;
vector<int>e[N],g[N];
int fat[N][25];
int dfn[N],dfncnt;
int sz[N],dep[N]; 
int T,k[N],kk[N];
int sta[2*N],top;
int ans[N];
struct dp_now{
    int f,mn;
}f[N];
vector<int>vir;
map<int,int>issp;
void dfs0(int p){ // 清空 dp 
    f[p].mn=INF,ans[p]=0;
    for(auto v:g[p])
        dfs0(v);
} 
void dfs(int p,int fa){
    dfn[p]=++dfncnt;
    sz[p]=1;
    for(int i=1;i<=20;i++)
        fat[p][i]=fat[fat[p][i-1]][i-1];
    for(auto v:e[p])if(v!=fa){
        dep[v]=dep[p]+1;
        fat[v][0]=p;
        dfs(v,p);
        sz[p]+=sz[v];
    }
}
int deps(int u,int v){
    if(dep[u]<dep[v])   
        swap(u,v);
    return dep[u]-dep[v];
}
void dfs2(int p){ // 子树的贡献 
    if(issp[p])
        f[p].f=p,f[p].mn=0;
    for(auto v:g[p]){
        dfs2(v);
        if(
            (f[v].mn+deps(v,p)<f[p].mn)||
            (f[v].mn+deps(v,p)==f[p].mn&&(f[p].f>f[v].f)) 
        )
            f[p].f=f[v].f,
            f[p].mn=f[v].mn+deps(v,p);
    }
    return;
}
void dfs3(int p,int fa){ // 父亲的贡献 
    if(fa){
        if(
            (f[fa].mn+deps(fa,p)<f[p].mn)||
            (f[fa].mn+deps(fa,p)==f[p].mn&&(f[p].f>f[fa].f)) 
        )
            f[p].f=f[fa].f,
            f[p].mn=f[fa].mn+deps(fa,p);            
    }
    ans[f[p].f]++;
    for(auto v:g[p])
        dfs3(v,p); 
    return;
}
pair<int,int> vs(int u,int v){ // 争抢客户 
    bool rev=0;
    if(dep[u]<dep[v])
        swap(u,v),rev=1;
    int umn=f[u].mn,newu=u;
    for(int i=20;i>=0;i--)
        if(umn<f[v].mn+dep[u]-dep[v]-(2<<i))
            f[fat[u][i]].f=f[u].f,
            u=fat[u][i],umn+=(1<<i);
    if(umn==f[v].mn+dep[u]-dep[v]-2&&f[u].f<f[v].f)
        u=fat[u][0];    
    int haveu=sz[u]-sz[newu];
    for(int i=20;i>=0;i--)if(dep[newu]-(1<<i)>dep[v])
        newu=fat[newu][i];
    int havev=sz[newu]-sz[u];
    if(rev) 
        swap(haveu,havev);
    return {haveu,havev};
}
void dfs4(int p){ // 虚树外的点   
    int son=sz[p]-1;
    for(auto v:g[p]){
        auto Give=vs(p,v);
        ans[f[p].f]+=Give.first;
        ans[f[v].f]+=Give.second;
        son-=(sz[v]+Give.first+Give.second);
        dfs4(v);
    } 
    ans[f[p].f]+=son;
}
void dfs5(int p){ // 清空虚树 
    for(auto v:g[p])
        dfs5(v);
    g[p].clear();
}
int LCA(int u,int v){
    if(dep[u]<dep[v])
        swap(u,v);
    for(int i=20;i>=0;i--)if(dep[u]-(1<<i)>=dep[v])
        u=fat[u][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--)if(fat[u][i]!=fat[v][i])
        u=fat[u][i],v=fat[v][i];
    return fat[u][0];
}
bool cmp(int u,int v){
    return dfn[u]<dfn[v];
}
void build(){
    cin>>T;
    issp.clear();
    vir.clear();
    for(int i=1;i<=T;i++)
        cin>>k[i],kk[i]=k[i],issp[k[i]]=1;
    sort(k+1,k+T+1,cmp);
    top=0;
    sta[++top]=1;
    for(int i=1;i<=T;i++)if(k[i]!=1){
        int lca=LCA(k[i],sta[top]);
        if(lca!=sta[top]){
            while(dfn[sta[top-1]]>=dfn[lca])
                g[sta[top-1]].push_back(sta[top]),
                --top;
            if(sta[top]!=lca)
                g[lca].push_back(sta[top]),
                sta[top]=lca; 
        }else;
        sta[++top]=k[i];
    }
    while(top>1)
        g[sta[top-1]].push_back(sta[top]),
        --top;  
    return;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    fat[1][0]=1;
    dfs(1,0);
    int m;
    cin>>m;
    while(m--){
        build();
        dfs0(1);
        dfs2(1);
        dfs3(1,0);
        dfs4(1); 
        for(int i=1;i<=T;i++)
            cout<<ans[kk[i]]<<" ";
        cout<<"\n";
        dfs5(1);
    }
    return 0;
}