[数据结构与算法]树、存储DFS/BFS序、树的直径

树

存储

链式前向星或者vector<edge>。图和树的存储方法一致。

有根树的DFS/BFS序

遍历一棵树的方法有两种：DFS/BFS。DFS是一直往深处走，在搜索过程中依次记录经过的点所生成的序列就是DFS序。DFS序不唯一。

DFN的求法：

#define pb push_back
std::vector<int> dfn; // dfn中的元素即为dfs序
std::vector<int> tree[maxn];
void dfs(int x) {
    dfn.pb(x);
    for(auto son:tree[x]) {
        dfs(son);
    }
}
int main(){
    int root=1; // 具体情况而定
    dfs(root);
}

有根树的BFS是按照层级顺序搜索，按照深度从小到大依次遍历所有的点。队列里元素出现的顺序就是BFS序。

BFS序求法：

#define pb push_back
std::vector<int> tree[maxn];
queue<int> q;
void bfs(int x) {
    q.push(x);
    while (!q.empty()) {
        int y=q.front();
        q.pop();
        for(auto son:tree[y]) {
            q.push(son);
        }
    }
}
int main(){
    int root=1; // 具体情况而定
    bfs(root);
}

无根树的DFS/BFS序

无根树中的节点只有相邻关系而没有父子关系。

遍历无根树时，可以从任意节点出发，像遍历有根树一样遍历整颗树。区别是要记录此节点的来源，以免无限递归再次访问。

树的直径

树上任意两个节点之间最长的距离(经过的边的数目)。路径不是唯一的。

树的直径的中间节点被称为树的中心，如果直径上有偶数个节点，那么中间两个点都是树的中心。**树的中心到其他点的最长路径最短。**树的中心是唯一确定的。

求直径的方法：从任意节点开始搜索距离其最远的点a，然后从a点开始重新搜索距离其最远的点b，则路径a-b即为树的直径之一。

例题

给你一棵树，让你求出这棵树的直径长度(直径经过的边的数量)。

树以下列方式给出：

• 输入第一行给出一个数 nn，表示一共有 nn 个节点；
• 接下来 n?1n?1 行，每行给出两个数 x,y(x≠y)x,y(x≠y)，表示 x,yx,y 之间有一条边。

输入格式

见题面。

输出格式

输出一个数，表示答案。

样例输入

4
1 2
1 3
3 4

样例输出

3

数据规模

对于所有数据，保证1≤n≤100000,1≤x,y≤n,x≠y1≤n≤100000,1≤x,y≤n,x≠y。

代码

一开始写的是链式前向星，结果超时了。后来换成vector就好了。

#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define debug(a) cout<<#a<<"="<<a<<endl;
inline ll rr(){ll f=1,x=0;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const int maxn=1e5+6;

int n,cnt;
int head[maxn],nxt[maxn],to[maxn];
int pre[maxn],dis[maxn];
std::vector<int> edge[maxn];
void add_edge(int u,int v) {
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}
void init() {
    n=rr();
    for(int i=1;i<n;i++) {
        int u=rr(),v=rr();
        edge[u].pb(v);
        edge[v].pb(u);
    }
}
void dfs(int u) {
    for(auto v:edge[u]) {
        if(v!=pre[u]) { // 不是其父
            pre[v]=u;
            dis[v]=dis[u]+1;
            dfs(v);
        }
    }
}
int main(){
    init();
    int minv=-1,idx=1;
    dfs(1);
    for(int i=1;i<=n;i++) {
        if(minv<dis[i]) {
            minv=dis[i];
            idx=i;
        }
    }
    for(int i=1;i<=n;i++) pre[i]=dis[i]=0;
    dfs(idx);
    minv=-1,idx=1;
    for(int i=1;i<=n;i++) {
        if(minv<dis[i]) minv=dis[i];
    }
    std::cout << minv << '\n';
}