## Codeforces Round 947 (Div. 1 + Div. 2) D. Paint the Tree 题解 DFS

news/2024/8/6 11:39:58/文章来源:https://blog.csdn.net/bbc_plus/article/details/139305556

## Paint the Tree

### 题目描述

378QAQ has a tree with n n vertices. Initially, all vertices are white.

There are two chess pieces called P A P_A and P B P_B on the tree. P A P_A and P B P_B are initially located on vertices a a and b b respectively. In one step, 378QAQ will do the following in order:

1. Move P A P_A to a neighboring vertex. If the target vertex is white, this vertex will be painted red.
2. Move P B P_B to a neighboring vertex. If the target vertex is colored in red, this vertex will be painted blue.

Initially, the vertex a a is painted red. If a = b a=b , the vertex a a is painted blue instead. Note that both the chess pieces must be moved in each step. Two pieces can be on the same vertex at any given time.

378QAQ wants to know the minimum number of steps to paint all vertices blue.

### 输入描述

Each test contains multiple test cases. The first line contains the number of test cases t t ( 1 ≤ t ≤ 1 0 4 1\leq t\leq 10^4 ). The description of the test cases follows.

The first line of each test case contains one integer n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 ).

The second line of each test case contains two integers a a and b b ( 1 ≤ a , b ≤ n 1\leq a,b\leq n ).

Then n − 1 n - 1 lines follow, each line contains two integers x i x_i and y i y_i ( 1 ≤ x i , y i ≤ n 1 \le x_i,y_i \le n ), indicating an edge between vertices x i x_i and y i y_i . It is guaranteed that these edges form a tree.

It is guaranteed that the sum of n n over all test cases does not exceed 2 ⋅ 1 0 5 2\cdot 10^5 .

### 输出描述

For each test case, output the minimum number of steps to paint all vertices blue.

#### 样例输入#1

3
2
1 2
1 2
5
1 2
1 2
1 3
1 4
1 5
8
5 4
7 1
1 5
1 8
8 3
7 2
8 6
3 4


#### 样例输出 #1

2
8
13


CF——传送门

### 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 2e5 + 6;
vector<int> e[maxn]; // e[i]存储以i为起点的所有有向边void add(int x, int y) // 加无向边
{e[x].push_back(y);e[y].push_back(x);
}int a, b;
deque<int> path; // 记录两颗棋子汇合的路径
int st = -1;     // 两颗棋子最快汇合后的点(也是dfs求max_dis的起点)
int step = 0;    // 汇合所需步数
int extra = 0;   // 两个棋子不可能位于同一个结点的情况(即两棋子异步)，此时需要补充1步
void dfs1(int pos, int fa, int depth, int tag)
{if (st != -1) // 如果已找到答案，快速返回return;for (int i = 0; i < e[pos].size(); i++){int to = e[pos][i];if (to == tag){step = (depth + 1) / 2;if (path.size() % 2 == 0) // 两棋子异步(即两棋子初始时距离为奇数，也就是最短路径上的结点为偶数个的情况){extra = 1;          // 补充1步path.push_front(a); // 特殊照顾一下两棋子初始时距离为1的情况，因为这种情况下st为a，但是path路径在dfs时并没有保存a结点st = path[step];}else // 两棋子同步(即两棋子初始时距离为偶数，也就是最短路径上的结点为奇数个的情况){st = path[step - 1];}return;}if (to == fa)continue;path.push_back(to);dfs1(to, pos, depth + 1, tag);path.pop_back(); // 回溯}
}int max_dis = 0; // 起点st到其他点的所有距离中的最远距离
void dfs2(int pos, int fa, int depth)
{max_dis = max(max_dis, depth); // 维护最远距离即可for (int i = 0; i < e[pos].size(); i++){int to = e[pos][i];if (to == fa)continue;dfs2(to, pos, depth + 1);}
}void solve()
{int n;cin >> n;cin >> a >> b;int x, y;for (int i = 1; i <= n - 1; i++){cin >> x >> y;add(x, y);}if (a != b)dfs1(a, 0, 0, b);elsest = a;dfs2(st, 0, 0);// 2 * (n - 1) - max_dis是用到了一个结论：从树中的一个结点开始走，走过树上所有结点至少需要2 * (n - 1) - max_dis步cout << step + 2 * (n - 1) - max_dis + extra << '\n';// 初始化，为了处理下一组测试数据for (int i = 1; i <= n; i++){e[i].clear();}path.clear();st = -1;dis = 0;max_dis = 0;extra = 0;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while (t--)solve();return 0;
}


### 深度神经网络——什么是生成式人工智能？

1.引言 生成式人工智能最近引起了很大的关注。 该术语用于指依赖无监督或半监督学习算法来创建新的数字图像、视频、音频和文本的任何类型的人工智能系统。 麻省理工学院表示&#xff0c;生成式人工智能是过去十年人工智能领域最有前途的进展之一。 通过生成式人工智能&#…

### 【车载开发系列】Autosar DEM中重要配置项说明

【车载开发系列】Autosar DEM中重要配置项目 【车载开发系列】Autosar DEM中重要配置项目说明 【车载开发系列】Autosar DEM中重要配置项目1&#xff09;DemDtcStatusAvailabilityMask2&#xff09;DemTypeOfDTCSupported3&#xff09;DemFreezeFrameCapture4&#xff09;DemIm…

### 前端菜鸡，对于35+程序员失业这个事有点麻了

“经常看到30岁程序员失业的新闻&#xff0c;说实话&#xff0c;有点麻。目前程序员供求关系并未失衡&#xff0c;哪怕是最基础的前端或者后台、甚至事务型的岗位也是足够的。 事实上&#xff0c;现在一个开出的岗位要找到一位尽职尽责能顺利完成工作的程序员并不是一件那么容…

### 2018 年山东省职业院校技能大赛高职组“信息安全管理与评估”赛项任务书

2018年山东省职业院校技能大赛高职组 “信息安全管理与评估”赛项任务书 赛项时间 8:30-13:00&#xff0c;共计4小时30分钟&#xff0c;含赛题发放、收卷时间。 赛项信息 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 第一阶段 平台搭建与安全设备配置防护 …