错误代码:
#include <bits/stdc++.h>
//#define int long long
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1
#define LL long long
#define ULL unsigned long long
using namespace std;
const int N = 1e5 + 5;
int hd[N], cnt, d[N], dep[N], fa[N][30];
struct Edge {
int to, nx;
} e[N << 1];
void add(int u, int v) {
e[ ++ cnt] = {v, hd[u]}, hd[u] = cnt;
}
void dfs(int u, int fat, int D) {
d[u] = dep[u] = D;
fa[u][0] = fat;
for (int i = hd[u]; i; i = e[i].nx) {
int v = e[i].to;
if (v == fat) continue;
dep[v] = dep[u] + 1;
dfs(v, u, D + 1);
d[u] = max(d[u], d[v]);
}
}
signed main() {
int n, x, k; cin >> n >> x >> k;
for (int i = 1; i < n; i ++) {
int u, v; cin >> u >> v;
add(u, v), add(v, u);
}
dfs(x, 0, 0);
for (int i = 1; i <= 29; i ++) {
for (int j = 1; j <= n; j ++) {
fa[j][i] = fa[fa[j][i - 1]][i - 1]; // 经典转移
}
}
int ans = 0;
for (int i = 1; i <= k; i ++) {
int p; cin >> p;
if (p == x) continue; // 特判!!!着火点和传送点在一起时不能计算贡献
int l = dep[p] / 2; // 最多能向上走 l 步
for (int j = 29; j >= 0; j --) {
if (l >= (1 << j)) { // 向上倍增
p = fa[p][j];
l -= (1 << j);
}
}
ans = max(ans, d[p]);
}
cout << ans;
return 0;
}
第 53 行
int l = dep[p] / 2;
应该是
int l = (dep[p] - 1) / 2;
但是两个都 AC 了
hack数据:
input:
15 1 1
10 2
2 1
10 11
11 12
12 13
13 14
14 15
10 6
6 7
7 8
8 9
6 5
5 4
5 3
5
正确代码output:
6
错误代码output:
7
如果是我造数据出了问题,很抱歉我浪费了你的时间,请打死我,否则请加强数据,谢谢。