C
题目保证是一个树,不存在环
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
vector<ll>v[N];
ll n,j,k,ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n-1;i++){
cin>>j>>k;
v[j].push_back(k);
v[k].push_back(j);
}//读入无向边
for(int i=1;i<=n;i++){
ll sum=0;
for(auto u:v[i]){
sum+=1;//加上每个临边
sum+=v[u].size()-1;//在加上临边的临边,减去i
}
if(sum==n-1) ans++;
}
cout<<ans<<endl;
return 0;
}
F
2024年6月7日01:03:12,太晚了不写了,b站讲的很详细
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
const int M=1000000007;
ll n,seed,i,j;
vector<ll>v[N];
ll rnd(){
ll ret=seed;
seed=(seed*7+13) % M;
return ret%2;
}
int main(){
cin>>n>>seed;
if(n==2) return cout<<"0",0;
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++){
if(rnd()==0)
v[i].push_back(j);
else v[j].push_back(i);
}
ll ans=n*(n-1)*(n-2)/6;
for(int i=1;i<=n;i++){
auto u=v[i].size();
ans-=u*(u-1)/2;
}
cout<<ans<<endl;
return 0;
}