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;
}