自动搬运

查看原文

来自洛谷，原作者为

	Reilher_lover qwqwq||这个家伙很菜||氢氦锂铍硼，碳氮氧氟氖，钠一天的犹豫，鱿鱼起来~

搬运于2025-08-24 23:17:13，当前版本为作者最后更新于2025-05-31 17:55:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

水题。

前置：换根 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}\} $$

$f_{y,1}$ 很好推，就不推了。

时间复杂度 $O(n)$。

Code

#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;
}