P9864 [POI2021~2022R2] age

· · 题解

前言：waauto 和 xzl 晚上 duel 这道题，于是晚上在床上想出了这道题。

题意

给定一些点，要把树分成几个连通块，每个连通块内要包含一个点，一个连通块的代价是边数乘 2 减去关键点到最远的点的距离。问全局代价最小值。

做法

首先讲一下为什么局部代价是这样。

假设我们已经找到了一个连通块划分方案，如果一个人走完了要回到原点，那么代价是边数乘 2。

由于不需要回到原点，我们可以走到最深的叶子结点就停下，所以减去最远点距离。

同时这个贡献可以看做有一条链上每条边的贡献是 1，其余是 2。

考虑 dp，设 f_{u,0/1,0/1} 表示目前节点是 u，所属关键点在子树内还是子树外，向父亲的边的贡献是 1 还是 2。

然后就是大力分讨转移。

代码里有详细注释。

时间复杂度 O(n)，不是很懂为什么开 3s。

代码

const int N=5e5+5;
int n,k;
vector<int> e[N];
bool vis[N];
int f[N][2][2];
/*
向上或者向下 单边或者双边 
f[u][0][0]:向上的单边 
if(!vis[u]){
f[v][0][0]+1+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1])
}
else{
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1])
} 
f[u][0][1]:向上的双边 
if(!vis[u]){
f[v][0][1]+2+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1])
f[v][0][0]+1+(f[other][1][1]+2)/(f[other][0][0])/(f[other][0][1]) 有一个可以是 f[other][1][0]+1 
}
else{
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1]) 有一个可以是 f[son][1][0]+1 
} 
f[u][1][0]:向下的单边 
if(!vis[u]){
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1]) 有一个可以是 f[son][1][0]+1
} 
else{
nope
}
f[u][1][1]:向下的双边 
if(!vis[u]){
(f[son][1][1]+2)/(f[son][0][0])/(f[son][0][1])
} 
else{
nope
}
*/
inline void dfs(int u,int fa){
    for(int v:e[u]) if(v!=fa) dfs(v,u);
    if(vis[u]){
        for(int v:e[u]) if(v!=fa) f[u][0][0]+=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));

        vector<int> g[2];
        F(i,0,1) g[i]=vector<int>(e[u].size()+1);
        F(i,0,int(e[u].size())-1){
            int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
            if(v!=fa){
                g[0][i+1]=g[0][i]+val;
                g[1][i+1]=min(g[1][i]+val,g[0][i]+min(val,f[v][1][0]+1));
            }else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
        }
        f[u][0][1]=g[1].back();

        f[u][1][0]=f[u][1][1]=1e9;
    }else{
        vector<int> g[4];
        F(i,0,1) g[i]=vector<int>(e[u].size()+1);
        g[1][0]=1e9;
        F(i,0,int(e[u].size())-1){
            int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
            if(v!=fa){
                g[0][i+1]=g[0][i]+val;
                g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][0]+1);
            }else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
        }
        f[u][0][0]=g[1].back();

        F(i,0,1) g[i]=vector<int>(e[u].size()+1);
        g[1][0]=1e9;
        F(i,0,int(e[u].size())-1){
            int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
            if(v!=fa){
                g[0][i+1]=g[0][i]+val;
                g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][1]+2);
            }else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
        }
        f[u][0][1]=g[1].back();

        F(i,0,3) g[i]=vector<int>(e[u].size()+1);
        g[1][0]=g[3][0]=1e9;
        F(i,0,int(e[u].size())-1){
            int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
            if(v!=fa){
                g[0][i+1]=g[0][i]+val;
                g[1][i+1]=min(g[1][i]+val,g[0][i]+f[v][0][0]+1);
                g[2][i+1]=min(g[2][i]+val,g[0][i]+min(val,f[v][1][0]+1));
                g[3][i+1]=min(g[3][i]+val,min(g[1][i]+min(val,f[v][1][0]+1),g[2][i]+f[v][0][0]+1));
            }else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i],g[2][i+1]=g[2][i],g[3][i+1]=g[3][i];
        }
        f[u][0][1]=min(f[u][0][1],g[3].back());

        F(i,0,1) g[i]=vector<int>(e[u].size()+1);
        F(i,0,int(e[u].size())-1){
            int v=e[u][i],val=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
            if(v!=fa){
                g[0][i+1]=g[0][i]+val;
                g[1][i+1]=min(g[1][i]+val,g[0][i]+min(val,f[v][1][0]+1));
            }else g[0][i+1]=g[0][i],g[1][i+1]=g[1][i];
        }
        f[u][1][0]=g[1].back();

        for(int v:e[u]) if(v!=fa) f[u][1][1]+=min(f[v][1][1]+2,min(f[v][0][0],f[v][0][1]));
    }
//  cout<<u<<' '<<f[u][0][0]<<' '<<f[u][0][1]<<' '<<f[u][1][0]<<' '<<f[u][1][1]<<'\n';
}
bool M2;
int main(){
    int Time=clock();
    look_memory;
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>k;
    F(i,1,k){
        int x;cin>>x;
        vis[x]=1;
    }
    F(i,1,n-1){
        int u,v;cin>>u>>v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    dfs(1,0);
    cout<<min(f[1][0][0],f[1][0][1])<<'\n';
    look_time;
    return 0;
}