牛啊 这次要快速读入 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;
}