trudbot

用户名：2185759039

访问量：5810

签　名：

等　　级
排　　名	9694
经　　验	1077
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

倍增LCA算法
浏览：1311

极简线性DP
浏览：2979

树上差分
浏览：732

你可能喜欢

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

树上差分

　　作者: trudbot　　　　发表时间：2023-04-12 20:19:53 浏览：732　|　评论：0　

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

## 试题J: 砍树

### 题意描述

给定一棵由n 个结点组成的树以及m 个不重复的无序数对$(a_1,b_1), (a_2,b_2),...,(a_m,b_m)$，其中$a_i$ 互不相同，$b_i$ 互不相同，$a_i \neq b_j$(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个$(a_i,b_i)$ 满足$a_i$和$b_i$ 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从1 开始），否则输出-1。

### 树上差分

同上题我们知道， 树中两个结点的简单路径是唯一的。

因此如果我们能找到一条边， 每组数对的两个结点的简单路径都要经过这条边， 那么就可以满足题意。

这时我们可以很简单的想到思路， 对于数对$(a, b)$， 我们遍历a到b路径上的每一条边， 让其权值加一。

最后若存在权值为m的边， 那么就满足题意。

但这样做时间复杂度显然最坏是$O(nm)$， 不达标。

这时候我们可以用到树上差分优化这一过程， 同理这里不会赘述它是什么， 请自行去学习[相关知识](https://www.cnblogs.com/TEoS/p/11376676.html)。

### 参考代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<pair<int, int>> g[N];
int dep[N], f[N][20], cnt[N], w[N];

void init(int u, int fa) {
  dep[u] = dep[fa] + 1, f[u][0] = fa;
  for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
  for (auto &e : g[u]) {
    if (e.first != fa) init(e.first, u), w[e.first] = e.second;
  }
}

int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int i = M; i >= 0; i --) {
    if (dep[f[a][i]] >= dep[b]) a = f[a][i];
    if (a == b) return a;
  }
  for (int i = M; i >= 0; i --) {
    if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
  }
  return f[a][0];
}

void add(int a, int b) {
  int LCA = lca(a, b);
  cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2;
}

void dfs(int u, int fa) {
  for (auto &e : g[u]) {
    if (e.first != fa) 
      dfs(e.first, u), cnt[u] += cnt[e.first];
  }
}

int main () {
  int n, m; cin >> n >> m;
  for (int i = 1; i < n; i ++) {
    int a, b; cin >> a >> b;
    g[a].push_back({b, i}), g[b].push_back({a, i});
  }
  init(1, 0);
  for (int i = 0; i < m; i ++) {
    int a, b; cin >> a >> b;
    add(a, b);
  }
  dfs(1, 0);
  int res = -1;
  for (int i = 1; i <= n; i ++) 
    if (cnt[i] == m && (w[i] > res)) res = w[i];
  cout << res << endl;
  return 0;
}
```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

trudbot

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

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

简单的a+b （C语言代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

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

树上差分

评论区

精彩推荐

矩形面积交（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

printf基础练习2 （C语言代码）

Tom数（C++代码）

简单的a+b （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

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

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

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

【亲和数】（C语言代码）

trudbot

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

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

简单的a+b （C语言代码）

三进制小数 （C++代码）（第11位大于1.5才能进位）

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

树上差分

评论区

精彩推荐

矩形面积交 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

printf基础练习2 （C语言代码）

Tom数 （C++代码）

简单的a+b （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

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

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

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

【亲和数】 （C语言代码）

汽水瓶（C语言代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

　　评论区

矩形面积交（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

Tom数（C++代码）

【亲和数】（C语言代码）