求树的直径

class Solution {
public:
    static const int maxn = 20;
    int head[maxn], to[maxn<<1], nex[maxn<<1], tot;
    void init() {
        memset(head, -1, sizeof(head));
        tot = 0;
    }
    void add(int x, int y) {
        to[tot] = y;
        nex[tot] = head[x];
        head[x] = tot++;
    }
    bool is[maxn], vis[maxn];
    int dis[maxn], maxd;//最长距离maxd
    int bfs(int u) {
        queue<int> que;
        while (!que.empty()) que.pop();
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        que.push(u);
        int max_num = 0;
        maxd = 0;
        while (!que.empty()) {
            int now = que.front(); que.pop();
            vis[now] = 1;
            for (int i = head[now]; ~i; i = nex[i]) {
                int v = to[i];
                if(vis[v] || !is[v]) continue;
                vis[v] = 1;
                dis[v] = dis[now] + 1;
                if(dis[v] > maxd) {
                    maxd = dis[v];
                    max_num = v;
                }
                que.push(v);
            }
        }
        return max_num;
    }
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
        int ans[20];
        init();
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            add(u, v);
            add(v, u);
        }
        for (int i = 3; i < (1<<n); i++) {
            int cnt = 0, pos;
            for (int j = 1; j <= n; j++) is[j] = 0;
            for (int j = 0; j < n; j++) {
                if(((i>>j)&1)) is[j + 1] = 1, cnt++, pos = j + 1;
            }
            int u = bfs(pos);
            int s = bfs(u);
            int tmp = 0;
            for (int j = 1; j <= n; j++) if(vis[j]) tmp++;
            if(tmp == cnt) ans[maxd]++;
        }
        vector<int> xx;
        for (int i = 1; i < n; i++)
            xx.push_back(ans[i]);
        return xx;
    }
}pp;

//树形dp可以处理负权，两遍bfs和dfs不能，但可以输出路径，而dp不行
//树形dp,找路径带权树上最长的路径长度
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int head[maxn], to[maxn<<1], nex[maxn<<1], tot, edge[maxn<<1], vis[maxn];
int dp[maxn];
void add(int x, int y, int z) {
    to[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot++;
}
int ans;
void dfs(int x) {
    vis[x] = 1;
    for (int i = head[x]; ~i; i = nex[i]) {
        int v = to[i];
        if(vis[v]) continue;
        dfs(v);
        ans = max(ans, dp[v] + dp[x] + edge[i]);
        dp[x] = max(dp[x], dp[v] + edge[i]);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(u, v, w);
    }
    dfs(1);
    printf("%lld\n", (ll)(11 + 10 + ans) * ans / 2);
}
两遍bfs求最长距离，第一遍求出最长的路径上的一个点，第二遍从这个点出发一定是最长的路径
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int head[maxn], to[maxn<<1], nex[maxn<<1], tot, edge[maxn<<1], vis[maxn];
int dis[maxn], maxd;//最长距离maxd
void add(int x, int y, int z) {
    to[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot++;
}
int bfs(int u) {
    queue<int> que;
    while (!que.empty()) que.pop();
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    que.push(u);
    int max_num = 0;
    maxd = 0;
    while (!que.empty()) {
        int now = que.front(); que.pop();
        vis[now] = 1;
        for (int i = head[now]; ~i; i = nex[i]) {
            int v = to[i];
            if(vis[v]) continue;
            vis[v] = 1;
            dis[v] = dis[now] + edge[i];
            if(dis[v] > maxd) {
                maxd = dis[v];
                max_num = v;
            }
            que.push(v);
        }
    }
    return max_num;
}
int main()
{
    memset(head, -1, sizeof(head));
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    int u = bfs(1);//第一遍求出的最长路径上的一个点
    int s = bfs(u);//
    printf("%lld\n", (ll)(11 + 10 + maxd) * maxd / 2);
}