3369. 三千米健身步道

#include<bits/stdc++.h>
using namespace std;
int n,x,y,rst;
int cnt[1001],fr[1000],to[1000];
int i;
int main()
{
    cin>>n;
    for(i=1;i<n;++i){
        cin>>x>>y;
        ++cnt[x],++cnt[y];
        fr[i]=x,to[i]=y;
    }
    for(i=1;i<n;++i){
        rst+=(cnt[fr[i]]-1)*(cnt[to[i]]-1);
    }
    cout<<rst;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
    //创建邻接表
typedef struct EdgeNode {
    int adjvex;
    int weight;
    struct EdgeNode *next;
} EdgeNode;
typedef struct VertexNode {
    int data;
    EdgeNode *FirstEdge;
} VertexNode, AdjList[1100];
typedef struct {
    AdjList adjList;
    int n_v, n_e;
} Graph;
void Creat_Adj_List (Graph *G) {
    cin >> G->n_v;
    G->n_e = G->n_v - 1;
            //如果改成更一般的模板的话 应该是cin >> G->n_v >> G->n_e
    for (int i=1; i <= G->n_v; ++i)
        G->adjList[i].FirstEdge = nullptr;
    int x, y;
    for (int i=0; i < G->n_e; ++i) {
        cin >> x >> y;
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = y;
        e->next = G->adjList[x].FirstEdge;
        G->adjList[x].FirstEdge = e;

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = x;
        e->next = G->adjList[y].FirstEdge;
        G->adjList[y].FirstEdge = e;
    }
}
    //以下开始深搜
int ans = 0;
bool vis[1100];
void DFS (Graph *G, int s, int len) {
    if (len == 3) {
        ++ans; return;
    }
    EdgeNode *p = G->adjList[s].FirstEdge;
    vis[s] = 1;
    while (p) {
        if (!vis[p->adjvex]) DFS(G, p->adjvex, len+1);
        p = p->next;
    }
}
int main()
{
    //freopen("testin.txt", "r", stdin);
    ios::sync_with_stdio(false);
    Graph G;
    Creat_Adj_List(&G);
    for (int i=1; i<=G.n_v; ++i) {
        DFS(&G, i, 0);
        memset(vis, 0, sizeof(vis));
    }
            //从所有顶点开始搜 每条可能的路径都被算了两遍
    cout << ans/2 << endl;
    return 0;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

vector<vector<int>> g;
int n;
bool visited[1010];
int ans = 0;

void dfs(int u, int depth) {
    if (depth == 4) {
        ans++;
        return ;
    }
    if (!g[u].empty()) {
        for (int it : g[u]) {
            if (!visited[it]) {
                visited[it] = true;
                dfs(it, depth + 1);
                visited[it] = false;
            }
        }
    }
}

int main() {
    cin >> n;
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = true;
        dfs(i, 1);
        visited[i] = false;
    }
    cout << ans / 2;
    return 0;
}