为了感激多头的[回复](https://www.luogu.com.cn/discuss/499463)，我特意来这里膜拜。然后~~发现这题似乎并不难~~发觉这道题解法很巧妙，思维难度不低，代码极其简单。
题意很清楚，就是至多能找到多少个符合条件三元组 $\{a,b,c\}$：
1. $c$ 是 $a\to b$ 的简单路径上编号最大的点。
2. $a,b,c$ 是不同的三个节点。
3. $a,b,c$ 仅能被使用一次。
- - -
接下来记录我的思考历程。
**编号最大**一词给了我启发，这也就是说明，这棵树编号为 $n$ 的节点要么就是 $\{a,b,c\}$ 中的 $c$，要么就干脆不用。
接下来我就思考：什么时候不用，什么时候用呢？
我们不妨假设一棵树中编号最大的节点就是根，输入时把编号小的当成编号大节点的儿子。
维护一个数组 ${size_i}$，表示以 $i$ 为根的树匹配完三元组后所剩的节点数。很显然有对于节点 $j$，$\sum[size_k>0]\ge 2$ 时就可以有一个三元组的 $c$ 为 $j$（$k$ 为 $j$ 儿子）。
再次因为输入时的特殊处理，惊奇的发现任意三元组 $\{a,b,c\}$ 中，$a,b$ 分别位于 $c$ 的两颗不同子树上！
但这样复杂度不可靠，所以使用并查集辅助维护 $size$，复杂度蜕变为 $O(n)$ 带点并查集常数，问题不大。
至此，题目结果水落石出。
- - -
我语文很差，如果没听懂借助代码理解。
```cpp
#include <vector>
#include <stdio.h>
std::vector<int> edge[200005];
int f[200005],sze[200005];
inline int find(int x){
while(x!=f[x])
x=f[x]=f[f[x]];
return x;
}
//这种写法复杂度正确的，并且通常比递归版优秀。
int main(){
int t,n,i,u,v,son,ans;
scanf("%d",&t);while(t--){
ans=0;
scanf("%d",&n);
for(i=1;i<=n;++i)
f[i]=i;
for(i=1;i<=n;++i)
sze[i]=1;//先假定每个点“自成一家”
for(i=1;i<=n;++i)
edge[i].clear();//多测不清空，抱灵两行泪/ll
for(i=1;i<n;++i){
scanf("%d %d",&u,&v);
if(u>v)
edge[u].emplace_back(v);
else
edge[v].emplace_back(u);//这四行就是后面那么多行的基础。
}
std::vector<int>::iterator it;
for(i=1;i<=n;++i){
son=0;
for(it=edge[i].begin();it<edge[i].end();++it){//遍历所有子树
if(sze[find(*it)])
++son;
sze[i]+=sze[find(*it)];//更新size
f[find(*it)]=i;//认祖宗
}
if(son>1){
sze[i]-=3;
++ans;
}//如果子树中空闲节点个数足够，就能造出一个三元组。
}
printf("%d\n",ans);
}
}
```