Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // POI - Hotels
- // incompleto (10/100) , para corrigir
- // codeforces.com/profile/trath
- // Tiago Souza
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long int
- #define eps (ll) 1e9
- #define mc (int) 1e4
- #define epsi (int) 1e3
- #define mp make_pair
- #define pb push_back
- #define F first
- #define S second
- struct star{
- int x, y , z;
- };
- vector<int> adj[mc];
- bool vis[mc];
- int dist[mc];
- int cont[mc];
- void dfs(int x){
- vis[x] = true;
- for(int i = 0;i<adj[x].size() ; i++){
- int v = adj[x][i];
- if(!vis[v]){
- vis[v] = true;
- dist[v] = dist[x] + 1;
- cont[dist[v]]++;
- }
- }
- }
- ll binomial(ll i, ll j){
- ll C[i+1][j+1];
- ll n , m;
- for(ll n = 0 ;n<=i;n++){
- for(ll m = 0;m<=min(j,n);m++){
- if(m ==0|| n == m){
- C[n][m] = 1;
- }
- else{
- C[n][m] = C[n-1][m-1] + C[n-1][m];
- C[n][m]%=(ll)1e9 + 7;
- }
- }
- }
- return C[i][j];
- }
- int main(){
- int n;
- cin>>n;
- for(int i = 1;i<n;i++){
- int x, y;
- cin>>x>>y;
- x-- , y--;
- adj[x].pb(y);
- adj[y].pb(x);
- }
- dist[0] = 0;
- ll resp = 0;
- for(int i = 0;i<n;i++){
- memset(vis, 0 , n + 1);
- memset(dist , 0 , mc);
- memset(cont , 0 , mc);
- dist[i] = 0;
- dfs(i);
- for(int j = 1;j<mc;j++){
- if(cont[j] >= 3){
- resp += binomial(cont[j] , 3);
- }
- }
- }
- cout<<resp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement