树的直径

问题描述:

输入：第 1 行输入整数 n，表示树的 n 个点。点的编号从 1 开始。后面 n – 1 行中每行输入 3 个整数a、b、w，表示点 a 和 b 之间有一条边，边长为 w。

输出：一个整数,表示树的直径。

做两次DFS（或BFS）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{ int to,w;};             //to: 边的终点 w:权值
vector<edge> e[N];                   //用邻接表存边
int dist[N];                         //记录距离
void dfs(int u,int father,int d){    //用dfs计算从u到每个子结点的距离
  dist[u]=d;
  for(int i=0;i<e[u].size();i++)
    if(e[u][i].to != father)         //很关键，这一句保证不回头搜父结点
    dfs(e[u][i].to, u, d + e[u][i].w);
}
int main(void){
  int n; cin>>n;                      //输入
  for(int i=0;i<n-1;i++){
    int a,b,w; cin>>a>>b>>w;
    e[a].push_back({b,w});            //a的邻居是b，边长w
    e[b].push_back({a,w});            //b的邻居是a
  }
  dfs(1,-1,0);                        //计算从任意点（这里用1号点）到树上每个结点的距离
  int s = 1;
  for(int i=1;i<=n;i++)               //找最远的结点s, s是直径的一个端点
    if(dist[i]>dist[s]) s = i;
  dfs(s,-1,0);                        //从s出发，计算以s为起点，到树上每个结点的距离
  int t = 1;
  for(int i=1;i<=n;i++)               //找直径的另一个端点t
    if(dist[i]>dist[t]) t = i;
  cout << dist[t]<<endl;              //打印树的直径的长度
  return 0;
}

笔记：树的直径就是找到两个相邻最远的节点，返回路径上的所有权值相加，第一次DFS从树根找到最远的节点，再从最远的节点第二次DFS，就找到树的直径

树形PD

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{int to,w; };        //to: 边的终点 w:权值
vector<edge> e[N];
int dp[N];                     //储存子树的最长路径
int maxlen = 0;
bool vis[N];                   //标记已遍历过
void dfs(int u){
  vis[u] = true;
  for(int i = 0; i < e[u].size(); ++ i){
    int v = e[u][i].to, edge = e[u][i].w; 
    if(vis[v]) continue;       //v已经算过
    dfs(v);
    maxlen = max(maxlen, dp[u] + dp[v] + edge);    //历史最长，u节点子树+v节点子树+u→v的权值
    //计算max{f[u]}。注意此时dp[u]不包括v这棵子树，下一行才包括
    dp[u] = max(dp[u], dp[v] + edge);              //计算dp[u]，此时包括了v这棵子树
  }
  return ;
}
int main(){
  int n; cin >> n;
  for(int i = 0; i < n-1; i++){
    int a, b, w; cin >> a >> b >> w;
    e[a].push_back({b,w});                        //a的邻居是b，路的长度w
    e[b].push_back({a,w});                        //b的邻居是a
  }
  dfs(1);                                         //从点1开始DFS
  cout << maxlen << endl;
  return 0;
}

笔记：树形PD可以处理负权边，dp[]储存从u节点出发最远的路径长度，也就是u子树的最长路径，maxlen实时储存遍历的最长路径