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