树的遍历
例题：树的重心
对树进行 dfs，处理每个节点作为重心的时候各个连通块点数最大值即可。
对于重心上面的连通块，可以用 \(n-\) 下面连通块点数和 \(-1\)。
实现
int dfs(int now)
{
vis[now] = 1;
int sum = 1,res = 0;
for(int i=0;i<Edge[now].size();i++)
{
int v = Edge[now][i];
if(!vis[v])
{
int t = dfs(v);
sum += t;
res = max(res,t);
}
}
res = max(res,n-sum);
if(res <= ans)
{
ans = res;
minn_num = now;
}
return sum;
}
求树的直径
法1：进行两次 dfs，任取一点先求出到它的最远距离，再从最远距离的那个点再跑一遍。
法2：树形 dp。显然直径上的点从它开始的最远距离和次远距离一定是直径的两个端点。求出每个节点开始走的最远距离和次远距离之和再取 max 即可。
实现（树形dp）
void dfs(int now,int fa)
{
for(int i=0;i<Edge[now].size();i++)
{
int v = Edge[now][i];
if(v == fa) continue;
dfs(v,now);
if(d1[v] + 1 > d1[now])
{
d2[now] = d1[now];
d1[now] = d1[v] + 1;
}
else if(d1[v] + 1 > d2[now]) d2[now] = d1[v] + 1;
}
}
实现（两遍dfs）
void dfs(int now,int fa,int dis)
{
for(int i=0;i<Edge[now].size();i++)
{
int v = Edge[now][i].first,w = Edge[now][i].second,u = now;
if(v == fa) continue;
dfs(v,now,dis+w);
}
int u = now;
d[u] = dis;
if(dis > tmp2)
{
tmp2 = dis;
tmp1 = u;
}
}
小应用：树的中心
常规思路这是一个换根 dp 板子，但只能用换根 dp 做吗？
结论： 树的中心一定在树的直径上。
证明：树的直径是树上的最长路径。而我们要求一个点在树上它到另一个点的最远距离最近。也就是直径上趋于中点。如果不在直径上则会走的更远（得先走到直径上）
因此，我们求出树的直径，接着求每个点距离树的直径两个端点的距离，取min即可。
实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PAIR;
const int N = 10010;
const int INF = 0x3f3f3f3f;
vector <PAIR> Edge[N];
int d1[N],d2[N];
int res = INF;
int n;
int tmp1,tmp2;
int d[N];
void dfs(int now,int fa,int dis)
{
for(int i=0;i<Edge[now].size();i++)
{
int v = Edge[now][i].first,w = Edge[now][i].second,u = now;
if(v == fa) continue;
dfs(v,now,dis+w);
}
int u = now;
d[u] = dis;
if(dis > tmp2)
{
tmp2 = dis;
tmp1 = u;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
Edge[u].push_back(PAIR(v,w));
Edge[v].push_back(PAIR(u,w));
}
dfs(1,0,0);
int pos1 = tmp1;
tmp2 = 0,tmp1 = 0;
dfs(pos1,0,0);
int pos2 = tmp1;
tmp2 = 0,tmp1 = 0;
for(int i=1;i<=n;i++) d1[i] = d[i]; //距离第一个端点的距离，次长
dfs(pos2,0,0);
for(int i=1;i<=n;i++)d2[i] = d[i]; //距离第二个端点的距离，不用memset，也就是求最长
int ans = 0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
if(ans > max(d1[i],d2[i])) ans = max(d1[i],d2[i]);
}
cout<<ans<<endl;
return 0;
}
可以发现很多题目都可以转换成直径相关！也算是一个小Trick吧（