树的直径模板 dfs / p3304

前言

在解决树的直径问题时，用到了一些性质，具体算法为： 从某一节点（如1节点）去找到据它最远的节点，那么这个节点一定在直径上 然后再从这个节点出发，寻找据此节点最远的节点，即为直径 由于树的特殊性（路径唯一），故可以仅用dfs完成搜索

一、例题，p3304

二、思路及代码 1.思路

第一问很好解决，直接dfs，记录ans 第二问则需要稍加思考，不过注意到所有树的直径都会经过圆心，那么就可以在一条直径上去dfs判断直径分岔，问题解决 开辟pre[]、path[] 和in[]数组记录一条直径上的节点

2.代码

代码如下 ：

#include 
#include 
#define ll long long
using namespace std;
const int maxn = 4e5 + 5;
int n, pre[maxn];
int cnt, head[maxn];
int num, path[maxn];
ll dis[maxn], mx[maxn];
bool in[maxn];
struct e {
  int to, next, cost;
} edge[maxn];
void init() {
  cnt = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i = dis[end]) end = cur;
  for (int i = head[cur]; i != -1; i = edge[i].next) {
    int v = edge[i].to, w = edge[i].cost;
    if (v != fa) DFS(v, cur, val + w, end);
  }
}
void dfs(int cur, int fa, ll val) {
  mx[cur] = val;
  for (int i = head[cur]; i != -1; i = edge[i].next) {
    int v = edge[i].to, w = edge[i].cost;
    if (v != fa && !in[v]) dfs(v, cur, val + w), mx[cur] = max(mx[cur], mx[v]);
  }
}
signed main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  scanf("%d", &n);
  init();
  int u, v, w;
  for (int i = 1; i