C++ – H1050 树中的最长路 树宽

题目链接

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 100;
const int MAXM = MAXN << 2;
struct node {
    int u, v, nxt;
} edge[MAXM];
int head[MAXN];
int tot, n, now;
int dist[MAXN];
void init() {
    tot = 0;
    memset(head, -1, sizeof head);
    memset(dist, -1, sizeof dist);
}
void add_edge(int u, int v) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}
int bfs(int u) {
    memset(dist, -1, sizeof dist);
    int ans = 0;
    queue<int> q;
    dist[u] = 0;
    q.push(u);
    while(!q.empty()) {
        int tmp = q.front();
        q.pop();
        for(int i = head[tmp]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            if(dist[v] == -1) {
                dist[v] = dist[tmp] + 1;
                if(ans < dist[v]) {
                    ans = dist[v];
                    now = v;
                }
                q.push(v);
            }
        }
    }
    return ans;
}
int main() {
    init();
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    int ans = bfs(1);
    ans = bfs(now);
    printf("%d\n", ans);
    return 0;
}