题解：P12666 [KOI 2023 Round 2] 草地上的蚁穴
Reilher_lover
·
·
题解
水题。
前置：换根 dp。
思路分析
加入边 (i,j) 后，树变为基环树。此时就是经典的基环树上的边最大独立集。
基环树上 dp 的一个经典做法是断环成链，我们删去加入边 (i,j)，分别以 i,j 为根节点做一遍树上的边最大独立集，设 f_i,f_j 分别表示 i,j 为根节点，不选 i,j 的边最大独立集，那么基环树上的边最大权独立集就是 \max\{f_i,f_j\}。
这样就得到了一个 O(n^2) 的法，首先以每个点为根节点做树上边最大独立集，求出所有 f_i，然后枚举每一对点对 (i,j)，如果 \max\{f_i,f_j\}=res（res 是原树上的边最大独立集），那么 (i,j) 就是合法方案的一种。
如果求出 f_i 后，其实统计答案可以优化到 O(n)，问题是如何快速求出所有 f_i，不难想到换根 dp。
设 f_{i,1/0} 表示以 i 为根，i 选/不选的最大独立集，设 g_{i,1/0} 表示在 i 的子树中，i 选/不选的最大独立集，假设 y 节点的父亲是 x。
如果我们已知 f_{x,1/0},g_{y,1/0}，如何计算 f_{y,0}？
首先，f_{y,0} 包含 g_{y,0}。
如果 x 不选，那么在 y 子树之外的贡献为 f_{x,0}-\max\{g_{y,0},g_{y,1}\}，不难想，主要思考 dp 自下而上转移选择那个决策，换根时撤销就可以。
如果 x 选，那么 y 子树之外的贡献为 f_{x,1}-g_{y,0}。
可以得到：
f_{y,0}\gets g_{x,0}+\max\{f_{x,0}-\max\{g_{y,0},g_{y,1}\},f_{x,1}-g_{y,0}\}
时间复杂度 $O(n)$。
# Code
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=250005;
vector<int>G[N];
int n,f[N][2],g[N][2],res;
long long ans,sum;
void add(int x,int y){
G[x].push_back(y);
}
void dfs1(int x,int fa){
g[x][1]=1,g[x][0]=0;
for(auto y:G[x]){
if(y==fa)continue;
dfs1(y,x);
g[x][0]+=max(g[y][1],g[y][0]);
g[x][1]+=g[y][0];
}
return;
}
void dfs2(int x,int fa){
for(auto y:G[x]){
if(y==fa)continue;
f[y][0]=g[y][0];
f[y][0]+=max(f[x][1]-g[y][0],f[x][0]-max(g[y][0],g[y][1]));
f[y][1]=g[y][1];
f[y][1]+=f[x][0]-max(g[y][0],g[y][1]);
dfs2(y,x);
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){
scanf("%d %d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,0);
f[1][0]=g[1][0],f[1][1]=g[1][1];
res=max(f[1][0],f[1][1]);
dfs2(1,0);
for(int i=1;i<=n;i++)if(f[i][0]==res)sum++;//统计答案随便做
for(int i=1;i<=n;i++){
if(f[i][0]==res)ans+=1ll*(n-1);
else ans+=sum;
}
printf("%lld\n",ans/2);
return 0;
}
```