作业介绍

树上问题

// 最后的路径一定是在直径上的
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = N * 2;
#define int long long
int n, s;
int head[N], ver[M], nxt[M], edge[M], tot;
int diameter;
bool flg[N]; // 标记点是不是直径上的点
int dis[N], last[N];
int start, ed;
int dis1[N]; // dis1[i] 从 i 出发，不经过直径上的点能到达的最远距离

void add(int u, int v, int w) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	edge[tot] = w;
}

void dfs(int u, int fa, int w) {
	dis[u] = dis[fa] + w;
	last[u] = fa;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		int w = edge[i];
		dfs(v, u, w);
	}
}

// 从点 u 出发， 不经过直径上的点能走到的最远的距离
int ans = 0;
int maxdis(int u, int fa, int w) {
	ans  = max(ans, w);
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		int nx = edge[i];
		if (flg[v])
			continue; // 不经过直径上的点
		if (v == fa)
			continue;
		maxdis(v, u, w + nx);
	}
	return ans;
}


signed main() {
	cin >> n >> s;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	// 两DFS 求直径
	dfs(1, 0, 0);
	start = 1;
	for (int i = 2; i <= n; i++)
		if (dis[i] > dis[start])
			start = i;
	dfs(start, 0, 0);
	ed = 1;
	for (int i = 2; i <= n; i++)
		if (dis[i] > dis[ed])
			ed = i;
	diameter = dis[ed];
	// 标记直径上的点
	for (int i = ed; i ; i = last[i])
		flg[i] = 1;
	// 计算 dis1 数组
	for (int i = ed; i ; i = last[i])
		dis1[i] = maxdis(i, 0, 0);
	int ans = 1e9;
	// 最后的一定是在直径上的
	// 遍历直径的是从 ed 到 start
	for (int l = ed, r = ed; r != start ; r = last[r]) {
		// 保证 l 到 r 的区间距离是 小于等于 s
		int t = l;
		// 单调队列优化，自己尝试实现一下
		while (dis[r] - dis[l] <= s && l)
			t = l, l = last[l];
		// t  - r  的范围内，距离值是小于等于 s 的
		int maxx = 0;
		for (int j = r; j != t; j = last[j])
			maxx = max(maxx, dis1[j]);
		maxx = max({maxx, dis[t], dis[ed] - dis[r]});
		ans = min(maxx, ans);
	}
	cout << ans;
	return 0;
}

// 新建道路，然后新建的道路只能走一次
// 如果原来是树，每个道路都是肯定会走过一次
// 走过的数量为 2*（n-1）
// 新建的道路的数量是 1 或者 2
// k =1 的时候，我们直接连接直径上的 两个点，这样直径上的所有的点都只用经过一次(形成环形)
// 最后的结果为 2*（n-1） - 直径 + 1
// k =2 的时候
// 1. 建路形成的环无公共边： 2*（n-1） - 环1的长度 - 环2的长度 +2
// 2. 建路形成的环有公共边：
//   走的边数  = 2*(n-1) -(环1路边数 - 公共边) -(环2路边数 - 公共边) + 2(新建立的边)
// 选择环：建立的第一个环肯定是直径 ； 然后标记直径上的边全部标记为 -1
//     接着在求树的最长直径，
//  最后化简成： 走过的边 = 2*(n-1) - 直径1 - 直径2 + 2新边



#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = N * 2;
int n, k;
int head[N], ver[M], nxt[M], tot;
int cnt, start, ed;
int dis[N], last[N];
int diameter1, diameter2;
bool diamerpath[N];

void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa, int w) {
	last[u] = fa;
	dis[u] = dis[fa] + w;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dfs(v, u, 1);
	}
}

void dp(int u, int fa) {
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dp(v, u);
	}
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		int w = diamerpath[u] && diamerpath[v] ? -1 : 1;
		diameter2 = max(diameter2,  dis[u] + dis[v] + w);
		dis[u] = max(dis[u], dis[v] + w);
	}
}

void road() {
	dfs(1, 0, 0);
	start = 1;
	for (int i = 2 ; i <= n; i++)
		if (dis[i] > dis[start])
			start = i;
	dfs(start, 0, 0);
	ed = 1;
	for (int i = 2; i <= n; i++) {
		if (dis[i] > dis[ed])
			ed = i;
	}
	diameter1 =  dis[ed];   // 求出最长直径
}


int main() {
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	road();
	if (k == 1)
		cout << 2 * (n - 1)  -  diameter1 + 1;
	else {
		for (int i = ed; i ; i = last[i])
			diamerpath[i] = 1;
		memset(dis, 0, sizeof dis);
		dp(1, 0);
		cout << 2 * (n - 1) - diameter1 - diameter2 + 2;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = N * 2;
#define int long long
int n;
int head[N], ver[M], nxt[M], edge[M], tot;
int diameter;
bool flg[N]; // 标记点是不是直径上的点
int dis[N], last[N];
int start, ed;

void add(int u, int v, int w) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	edge[tot] = w;
}

void dfs(int u, int fa, int w) {
	dis[u] = dis[fa] + w;
	last[u] = fa;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		int w = edge[i];
		dfs(v, u, w);
	}
}

// 从点 u 出发， 不经过直径上的点能走到的最远的距离
int ans = 0;
int maxdis(int u, int fa, int w) {
	ans  = max(ans, w);
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		int nx = edge[i];
		if (flg[v])
			continue; // 不经过直径上的点
		if (v == fa)
			continue;
		maxdis(v, u, w + nx);
	}
	return ans;
}


signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	// 两DFS 求直径
	dfs(1, 0, 0);
	start = 1;
	for (int i = 2; i <= n; i++)
		if (dis[i] > dis[start])
			start = i;
	dfs(start, 0, 0);
	ed = 1;
	for (int i = 2; i <= n; i++)
		if (dis[i] > dis[ed])
			ed = i;
	diameter = dis[ed];
	cout << diameter << endl;
	// 标记一下直径上所有的点
	for (int i = ed ; i ; i = last[i])
		flg[i] = 1;
	int l = start, r = ed;
	for (int i = ed; i ; i = last[i]) {
		ans = 0;
		if (dis[ed] - dis[i] == maxdis(i, 0, 0))
			r = i;
		if ( dis[i] == maxdis(i, 0, 0)  && l == start)
			l = i;
	}
	// 求出公共边的数量
	int common = 0;
	for (int i = r; i != l ; i = last[i])
		common++;
	cout << common;
	return 0;
}

//  k =1   2*(n-1) -直径 +1
//  k = 2 的时候
//  1. 求出直径1 的长度
//  2. 直径上所有边标记为 -1，标记点，flg[u]=1 && flg[v]=1
//  3. 再去求直径 2 的长度
//   res = 2*(n-1)-直径1-直径2 + 2

// 并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int M = N * 2;
int n, m, q;
int head[N], ver[M], nxt[M], tot;
int fa[N];

void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

int find(int x) { // 并查集
	if (x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}

bool vis[N];
int diameter[N];  // 直径长度
int d[N];  // d[x] 从 x 出发能到达的最远的点的距离
int ans;
void dp(int x) { // 树形 DP 求直径长度
	vis[x] = 1;
	for (int i = head[x] ; i  ; i = nxt[i]) {
		int  y  = ver[i];
		if (vis[y])
			continue;
		dp(y);
		ans = max(ans, d[x] + d[y] + 1);
		d[x] = max(d[x], d[y] + 1);
	}
	diameter[x] = ans;
}

int main() {
	cin >> n >> m >> q;
	// 并查集初始化
	for (int i = 1 ; i <= n; i++)
		fa[i] = i;
	for (int i = 1 ; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
		u = find(u), v = find(v);
		fa[v] = u;
	}
	// 求所有树的直径，只需要对根求直径、  fa[i] =i
	for (int i = 1 ; i <= n; i++) {
		if (i == fa[i])
			ans = 0, dp(i);
	}
	while (q--) {
		int opt, x, y;
		cin >> opt >> x;
		if (opt == 1) {
			x = find(x);
			cout << diameter[x] << endl;
		} else {
			cin >> y;
			x = find(x), y = find(y);
			if (x == y)
				continue;
			else {
				fa[x] = y;
				diameter[y] = max({diameter[x], diameter[y], (diameter[x] + 1) / 2 + (diameter[y] + 1) / 2 + 1});
			}
		}
	}
	return 0;
}

直径参考代码1

// 求树的直径
// 输出直径上的点
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = N * 2;
int n;
int head[N], ver[M], nxt[M], tot;
int dis[N];
int start, ed;

int last[N];  //  记录直径
void  add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa, int flg) {
	dis[u] = dis[fa] + 1;
	if (flg == 2)
		last[u] = fa;
	for (int i = head[u] ; i  ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa)
			continue;
		dfs(v, u, flg);
	}
}

int main() {
	cin >> n;
	for (int i = 1 ; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0, 1);
	start = 1;
	for (int i = 2; i <= n; i++)
		if (dis[i] > dis[start])
			start = i;
	dis[0] = -1;
	dfs(start, 0, 2);
	ed = 1;
	for (int i = 2 ; i <= n; i++)
		if (dis[i] > dis[ed])
			ed = i;
	cout << dis[ed] << endl;
	// 直径上的点
	for (int i = ed; i ; i  = last[i])
		cout << i << " ";
	return 0;
}

M

// 如果是有唯一的重心，
// 随便删除一条边，再加入这条边
// 如果有两个重心，那么删除其中一个重心的一个叶子边
// 然后将这个叶子直接连接到最后保留的重心上
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = N * 2;
int T, n;
int head[N], ver[M], nxt[M], tot;
vector<int> center;
int siz[N], maxsub[N];
int leaffather, leaf;   // 要删除的叶子和叶子节点的父亲
void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa) {
	siz[u] = 1;
	maxsub[u] = 0;
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if ( v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
		maxsub[u] = max(maxsub[u], siz[v]);
	}
	maxsub[u] = max(maxsub[u], n - siz[u]);
}

void centercnt() {
	for (int i = 1 ; i <= n; i++) {
		if (maxsub[i] <= n / 2)
			center.push_back(i);
	}
}

// 找到一个叶子节点和一个他的父节点
void find(int u, int fa) {
	for (int i = head[u] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		find(v, u);
		return ;
	}
	leaf = u;
	leaffather = fa;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n;
		memset(head, 0, sizeof head);
		memset(siz, 0, sizeof siz);
		memset(maxsub, 0, sizeof maxsub);
		tot = 0;
		center.clear();
		for (int i = 1 ; i < n; i++) {
			int u, v;
			cin >> u >> v;
			add(u, v), add(v, u);
		}
		dfs(1, 0);
		centercnt(); // 数一下重心的数量
		if (center.size() == 1) {
			cout << center[0] << " " << ver[head[center[0]]] << endl;
			cout << center[0] << " " << ver[head[center[0]]] << endl;
		} else { // 如果有两个重心，一个作为父节点一个作为子节点
			find(center[0], center[1]);
			cout << leaffather << " " << leaf << endl;
			cout << center[1] << " " << leaf << endl;
		}
	}
	return 0;
}

DFS order

 DFS 树
 要知道每个节点在 DFS 顺序中
 可能出现的最小位置和最大位置

 最小位置：其实就是深度  dep

 最大位置：n - siz[x] +1

最远点对

直径的定义：相距最远的两个点的距离
f[x][2] : f[x][0],距离 x 最远的白点的距离
f[x][1] 距离 x 最远的黑点的距离

只有一个点, 初始化
x 是黑点 f[x][1] =0      f[x][0] = -1e9
x 是白点 f[x][1] = -1e9  f[x][0] = 1

ans = max({ans , f[x][1] + f[y][0] + 1 , f[x][0] +f[y][1] + 1})

f[x][1] = max(f[x][1]  , f[y][1] +1) , x 后面接了 y 
f[x][0] = max(f[x][0] , f[y][0] +1)


// 树的直径 DP 求法
// 树上DP
// d[x] 从节点 x 出发走向以  x 为根的子树，能够到达的最远节点的距离
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const  int M = N * 2;
int n;
int head[N], ver[M], nxt[M], tot;
int d[N], ans;
bool vis[N];

void add(int u, int v) {
	tot++;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dp(int x) {
	vis[x] = 1;
	for (int i = head[x] ; i ; i = nxt[i]) {
		int v = ver[i];
		if (vis[v]) continue;  // 必然不会经过之前经过的点
		dp(v);
		ans = max(ans, d[x] + d[v] + 1);
		d[x] = max(d[x], d[v] + 1);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dp(1);
	cout << ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N  = 5e4 + 10;
const int M = N * 2;
int n, pos, ans = 1e9;
int head[N], ver[M], nxt[M], tot;
bool v[N];
int size[N];

void add(int u, int v) {
	++tot;
	ver[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

// 树的重心
void dfs(int x) {
	v[x] = 1, size[x] = 1;
	int max_part = 0;
	for (int i = head[x] ; i ; i = nxt[i]) {
		int y = ver[i];
		if (v[y])
			continue;
		dfs(y);
		size[x] += size[y];
		max_part = max(max_part, size[y]);
	}
	max_part = max(max_part, n - size[x]);
	//
	if (max_part < ans || (max_part == ans && pos > x)) {
		ans = max_part; // 全局变量 ans 记录中心对应的 max_part
		pos = x; // 全局变量 pos 记录了重心
	}
}

int res = 0;
int dep[N];

void dfs1(int x, int fa) {
	dep[x] = dep[fa] + 1;
	res += dep[x];
	for (int i = head[x] ; i ; i = nxt[i]) {
		int y = ver[i];
		if (y == fa)
			continue;
		dfs1(y, x);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1);
	dep[0] = -1;
	dfs1(pos, 0);
	cout << pos << " " << res;
	return 0;
}

// 树的重心, 带点权
void dfs(int x) {
	v[x] = 1, size[x] = c[x]; // 带上点权
	int max_part = 0;
	for (int i = head[x] ; i ; i = nxt[i]) {
		int y = ver[i];
		if (v[y])
			continue;
		dfs(y);
		size[x] += size[y];
		max_part = max(max_part, size[y]);
	}
	max_part = max(max_part, n - size[x]);
	//
	if (max_part < ans || (max_part == ans && pos > x)) {
		ans = max_part; // 全局变量 ans 记录中心对应的 max_part
		pos = x; // 全局变量 pos 记录了重心
	}
}

int res = 0;
int dis[N];

void dfs1(int x, int fa, int w) {
	dis[x] = dis[fa] + w;
	res += dis[x];
	for (int i = head[x] ; i ; i = nxt[i]) {
		int y = ver[i];
		if (y == fa)
			continue;
		dfs1(y, x,edge[i]);
	}
}
// 重心, 带点权
// 计算每个点到重心的距离
// res += c[i]*dis[i];

题目

认领作业后才可以查看作业内容。
状态
正在进行…
题目
21
开始时间
2026-5-13 0:00
截止时间
2026-6-30 23:59
可延期
24 小时
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.1 Community