简单树上问题

一、树的直径

1.两次DFS求树的直径

B4016 树的直径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

先随便找一个点a，DFS一次找到最远距离的点u，再以u为起点DFS一次找到最远距离的点v，u到v即为树的直径

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
vector<int> g[N];
int d[N];void dfs(int now, int fa, int dep){d[now] = dep;for(auto &nex : g[now]){if(nex == fa) continue;dfs(nex, now, dep + 1);}
}int main() {int n; cin >> n;for(int i = 1; i <= n - 1; i++){int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, -1, 0);int s = 1;for(int i = 1; i <= n; i++){if(d[i] > d[s]) s = i;}dfs(s, -1, 0);int t = 1;for(int i = 1; i <= n; i++){if(d[i] > d[t]) t = i;}cout << d[t];
}

2.树形DP求树的直径

可以用于处理负权边

vector<int> g[N];
int dp[N], len;
void dfs(int now, int fa){for(auto &nex : g[now]){if(nex == fa) continue;dfs(nex, now);len = max(len, dp[now] + dp[nex] + 1);dp[now] = max(dp[now], dp[nex] + 1);		}
}

二、应用

1.距离问题

除直径两个端点以外，树中剩下的点所在的最长弦为该点到端点u的弦或者端点v的弦

Problem - 1805D - Codeforces

#include<bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
vector<int> g[N];
int d[N], dd[N], ans[N];void dfs(int now, int fa, int dep){d[now] = dep;for(auto &nex : g[now]){if(nex == fa) continue;dfs(nex, now, dep + 1);}
}
void dfs2(int now, int fa, int dep){dd[now] = dep;for(auto &nex : g[now]){if(nex == fa) continue;dfs2(nex, now, dep + 1);}
}int main() {int n; cin >> n;for(int i = 1; i <= n - 1; i++){int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, -1, 0);int s = 1;for(int i = 1; i <= n; i++){if(d[i] > d[s]) s = i;}dfs(s, -1, 0);int t = 1;for(int i = 1; i <= n; i++){if(d[i] > d[t]) t = i;}dfs2(t, -1, 0);for(int i = 1 ; i <= n ; i++)	if(i != t)	ans[max(d[i] , dd[i]) + 1]++ ;ans[0] = 1 ;for(int i = 1 ; i <= n ; i++)	ans[i] += ans[i - 1] , cout << ans[i] << ' ' ;
//	for(int i = 1; i <= n; i++){
//		cout << d[i] << ' ' << dd[i] << '\n';
//	}
}

2.记录直径上的点

用一个pre数组来记录每个点的先导点

Problem - 1294F - Codeforces

#include<bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
vector<int> g[N];
int d[N], pre[N];
bitset<N> vis;
int k, s, t;void dfs(int now, int fa, int dep){d[now] = dep;if(vis[now]) d[now] = 0, dep = 0;if(d[now] > d[k] && now != s && now != t){k = now;}pre[now] = fa;for(auto &nex : g[now]){if(nex == fa) continue;dfs(nex, now, dep + 1);}
}int main() {int n; cin >> n;for(int i = 1; i <= n - 1; i++){int u, v; cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, -1, 0);s = k;k = 0;dfs(s, -1, 0);t = k;k = 0;int temp = t;vector<int> path;path.push_back(t);while(pre[temp] != -1){path.push_back(pre[temp]);temp = pre[temp];}for(auto &i : path) vis[i] = true;int ans = d[t];
//	for(int i = 1; i <= n; i++) d[i] = 0;dfs(s, -1, 0);ans += d[k];
//	for(int i = 1; i <= n; i++) cout << d[i] << ' ';
//	cout << '\n';cout << ans << '\n';if(k == 0){for(int i = 1; i <= n; i++){if(i != s && i != t){k = i;break;}}}cout << s << ' ' << t << ' ' << k;
}

3.和并查集一起拷打

并查集判断是否连通，合并计算新直径时一种结果为取原来图中的大直径，另一种为连接两个图直径的中点

Problem - 455C - Codeforces

#include<bits/stdc++.h>
using namespace std;
#define qio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef long long ll;const int N = 3e5 + 10;
int pre[N];
int root(int x){return pre[x] = (pre[x] == x ? x : root(pre[x]));
}
void merge(int u, int v){pre[root(u)] = root(v);
}
bool isCon(int u, int v){return root(u) == root(v);
}vector<int> g[N];
int dp[N], len;
void dfs(int now, int fa){for(auto &nex : g[now]){if(nex == fa) continue;dfs(nex, now);len = max(len, dp[now] + dp[nex] + 1);dp[now] = max(dp[now], dp[nex] + 1);		}
}
bitset<N> vis;
ll c[N];
ll caldep(int x){len = 0;dfs(x, -1);return len;
}int main() {int n, m, q; cin >> n >> m >> q;for(int i = 1; i <= n; i++) pre[i] = i;for(int i = 1; i <= m; i++){int u, v; cin >> u >> v;merge(u, v);g[u].push_back(v);g[v].push_back(u);}for(int i = 1; i <= n; i++){if(pre[i] != i || vis[i]) continue;c[i] = caldep(i);vis[i] = true;}
//	for(int i = 1; i <= n; i++) cout << c[i] << '\n';while(q--){int op; cin >> op;if(op == 2){int u, v; cin >> u >> v;if(isCon(u, v)) continue;ll t = (c[root(u)] + 1) / 2 + (c[root(v)] + 1) / 2 + 1;t = max(t, max(c[root(u)], c[root(v)]));merge(u, v);c[root(u)] = t;}else{int x; cin >> x;cout << c[root(x)] << '\n';}}}