自动搬运

查看原文

来自洛谷，原作者为

	dottle Cy@?g|^a

搬运于2025-08-24 22:40:05，当前版本为作者最后更新于2022-09-05 19:12:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们考察整棵树上编号最大的点 $X$。对于经过 $X$ 的所有路径，都应当选取 $X$ 作为最大值。去掉 $X$，将树切成了若干子树，递归进子树内解决原问题。然后对于这些子树，如果有至少两个子树内还有没进三元组的点，就他们和 $X$ 作为一个三元组。

直接做是 $n^2$ 的，我们不妨逆序地考虑。从小到大地加入每个点，每次加入点的时候把和它相邻的、已经加入了的点合并在一起。维护每一个连通块的最大三元组个数和总大小，未匹配点的个数可以根据前两个信息方便地计算。

时间复杂度 $O(n\alpha (n))$，其中 $\alpha(n)$ 是并查集复杂度。

#include<bits/stdc++.h>
const int N=1000050;
using namespace std;

int n,res;
int fa[N],rest[N];
int gf(int k){return k==fa[k]?k:fa[k]=gf(fa[k]);}
vector<int> e[N];

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)fa[i]=i,rest[i]=1,e[i].clear(),res=0;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		e[max(x,y)].push_back(min(x,y));
	}
	for(int k=1;k<=n;k++){
		int c=0;
		for(auto to:e[k]){
			c+=!!rest[gf(to)];
			rest[k]+=rest[gf(to)];
			fa[gf(to)]=k;
		}
		if(c>=2)rest[k]-=3,res++;
	} 
	cout<<res<<endl;
}

main(){
	ios::sync_with_stdio(false);
	int _T=1;cin>>_T;
	while(_T--)solve();
}