牛啊 这次要快速读入 memset代价太高了 https://www.luogu.com.cn/paste/vg035rgp

问题模型 给定一棵树，求其中蒲公英的个数。

模型分析 对于一个点 uu，假设 uu 的孩子结点有 kk 个，它们分别是 v_{1\cdots k}v 1⋯k ​ ，首先特判掉 k<3k<3 不产生贡献的情况。

然后考虑枚举点 vv 不作为 单点的子树，作为链的起点：

此时这个 vv 对于点 uu 的贡献，是以 vv 为根的子树大小减一（链的长度不少于 22，所以 vv 自己作为链的情况需要去除）。 考虑列出式子：

\begin{aligned}&~~\sum_{foreachv}size[v]-1\=&~~n-1-du[u]\end{aligned}

​

for each v ∑ ​ size[v]−1 n−1−du[u] ​

其中 size[v]size[v] 表示以 vv 为根的子树大小，du[u]du[u] 表示点 uu 的度。

这个等式就是考虑容斥，把不可能作为“链”的末端的点（所有与 uu 直接相连的点和 uu 本身）去掉即可。

总复杂度 O(n)O(n)。

#include <bits/stdc++.h>
using namespace std;
const int N =2e6+10;
typedef long long ll;
int n,t,u,v;
int a[200006];
ll ans =0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >>n;
    while(n--){
        for(int i =1;i<=t;i++)a[i]=0;
        cin >>t;
        ans =0;
        for(int i=1;i<t;i++){
            cin >> u>>v;
            a[u]++,a[v]++;
        }
        for(int i =1;i<=t;i++){
            if(a[i]>=3){
                ans+=t-1-a[i];//每个顶点有n-1个子树    -去掉一个点
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}