计科余定成

用户名：dotcpp0598358

访问量：15773

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

图的遍历-DFS
浏览：56

求具有abcd=(ab+cd)2性质的四位数
浏览：73

[NOIP2004]合并果子
浏览：89

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

蓝桥杯2023年第十四届省赛真题-砍树（树上差分）

　　作者: 计科余定成　　　　发表时间：2023-04-25 20:15:47 浏览：509　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-砍树

# 解题思路
对于每一对 $$(a_i , b_i)$$，$$a_i$$ 到$$b_i$$之间的边都可以砍掉；
把可以砍掉的边权值+1，那么这条边的权值$$w$$表示砍掉这条边可以满足$$w$$对$$(a_i , b_i)$$不连通;
最后找到权值等于$$m$$且编号最大的删去即可，若没找到则代表无解；

# 例样讲解
例样的树
```cpp
1 2
2 3
4 3
2 5
6 5
```
![](/image_editor_upload/20230411/20230411103244_78316.png)
对于（3，6）
![](/image_editor_upload/20230411/20230411104150_12368.png)
对于（4，5）
![](/image_editor_upload/20230411/20230411104235_84595.png)
找到权值等于m且编号最大的边，即为4

# 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n, m;
int s[N], id[N];
ll deep[N], f[N][25];
ll ans = -1;
struct edge {
	ll id, next;
};
vector<edge>g[N];
void dfs(int u, int fa) {
	deep[u] = deep[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; (1 << i) <= deep[u]; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for (int i = 0; i < g[u].size(); i++) {
		if (g[u][i].next != fa) {
			dfs(g[u][i].next, u);
			id[g[u][i].next] = g[u][i].id;
		}
	}
}
int lca(int x, int y) {
	if (deep[x] < deep[y]) swap(x, y);
	for (int i = 20; i >= 0; i--) {
		if (deep[f[x][i]] >= deep[y]) x = f[x][i];
		if (x == y) return x;
	}
	for (int i = 20; i >= 0; i--) {
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	}
	return f[x][0];
}
void add(int x, int y) {
	s[x]++;
	s[y]++;
	s[lca(x, y)] -= 2;
}
void sum(int u, int fa) {
	for (int i = 0; i < g[u].size(); i++) {
		if (g[u][i].next != fa) {
			sum(g[u][i].next, u);
			s[u] += s[g[u][i].next];
		}
	}
}
int main() {
	cin >> n >> m;
	int u, v;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		g[u].push_back({i, v});
		g[v].push_back({i, u});
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		add(u, v);
	}
	sum(1, 0);
	for (int i = 1; i <= n; i++) {
		if (s[i] == m && id[i] > ans) ans = id[i];
	}
	cout << ans;
	return 0;
}

```

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-进制转换（C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

蓝桥杯2023年第十四届省赛真题-砍树（树上差分）

评论区

精彩推荐

汽水瓶（C语言代码）怎么答案错误？？？？？

IP判断（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-进制转换 （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

蓝桥杯2023年第十四届省赛真题-砍树（树上差分）

评论区

精彩推荐

汽水瓶 （C语言代码）怎么答案错误？？？？？

IP判断 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

C二级辅导-进制转换（C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

　　评论区

汽水瓶（C语言代码）怎么答案错误？？？？？

IP判断（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）