树的直径

树的直径

mi0e

January 8, 2023

898 views

No comments

1999 words

C/C++ 算法

# DFS

```c++
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

struct Node{
	int id, w;
};

vector<Node> m[N];
int dist[N];
int n;

void dfs(int idx, int root, int dst){
	dist[idx] = dst;
	for(auto node : m[idx])
		if(node.id != root)	dfs(node.id, idx, dst + node.w);
}

int main(){
	int p, q, d, t;
	cin >> n;
	t = n - 1;
	while(t--){
		scanf("%d%d%d", &p, &q, &d);
		m[p].push_back({q, d});
		m[q].push_back({p, d});
	}
	dfs(1, -1, 0);
	int idx = 1;
	for(int i = 1; i <= n; i++)
		if(dist[i] > dist[idx]) idx = i;
	dfs(idx, -1, 0);
	for(int i = 1; i <= n; i++)
		if(dist[i] > dist[idx]) idx = i;
	idx = dist[idx];
	printf("%lld", 10 * idx + (1ll + idx) * idx / 2);

return 0;
}
```

# BFS

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n;
int dist[N];
int h[N], e[N], ne[N], w[N], idx;

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void bfs(int x){
    queue<int> q;
    q.push(x);
  
    while (q.size()) {
        int t = q.front();
        q.pop();
      
        if (st[t]) continue;
        st[t] = true;
      
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                dist[j] = dist[t] + w[i];
                q.push(j);              
            }
        }
    }
}

int main(){
    scanf("%d", &n);
  
    int a, b, c;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
  
    bfs(1);
    int idx = 1, res = 0;
    for (int i = 1; i <= n; i++)
        if (res < dist[i]) idx = i, res = dist[i];
    memset(st, 0, sizeof st);
    memset(dist, 0, sizeof dist);  
    bfs(idx);
    res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dist[i]);
    printf("%lld", res * 10 + (1ll + res) * res / 2) ;
  
    return 0;
}
```

# 树形DP

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, res;
int h[N], e[N], ne[N], w[N], idx;

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dfs(int p, int father){
    int d1 = 0, d2 = 0;
  
    for (int i = h[p]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        int d = dfs(j, p) + w[i];
      
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    res = max(res, d1 + d2);
    return d1;
}

int main(){
    scanf("%d", &n);
  
    int a, b, c;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
  
    dfs(1, -1);
    printf("%lld", 10 * res + (1ll + res) * res / 2);

return 0;
}
```

Last modification：March 13, 2023