Codeforces-832D-Misha, Grisha and Underground

题目链接：

codeforces-832D

题目大意：

给一个 n 个节点的树，然后q个询问，每一个询问给三个节点 a,b,c 。 你可以选择其中一个节点，求另外两个点到这个点的 公共路径上的 最大点数？

数据范围：

2≤n≤1e5，1≤q≤1e5

解题思路：

可以将求点数转化为求边数，因为是树，所以点数就等于边数+1，而边数就是路径长度。 看到一个求公共路径长度的公式： 用 dist(x,y) 表示 x 节点 到 y 节点的长度。 若选择节点 a， 那么 c -> a 和 b –>a 的公共路径长度为： [dist(c,a)+dist(b,a)–dist(b,c)]/2 这个画个图出来稍微想一想就知道了。选择 b 或 c的以此类推。 至于求两点之间的距离，用LCA就可以了。 最后就只需要依次选择 a,b,c取个 MAX就好。

这道题刚好，复习了一下LCA，确实忘得差不多了。电脑里还没LCA的板子，一会儿过去写一份。

AC代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int MaxN = 1e5; int n, q, all; int pre[2 * MaxN + 5], last[MaxN + 5], other[2 * MaxN + 5]; int dep[MaxN + 5]; int up[MaxN + 5][22]; //up[i][j]表示i节点向上走2的j次方步所能到达的点 void build(int x, int y) { pre[++all] = last[x]; last[x] = all; other[all] = y; } void Dfs(int x, int fa) { dep[x] = dep[fa] + 1; up[x][0] = fa; for(int i = 1; i <= 20; i++) up[x][i] = up[up[x][i - 1]][i - 1];//更新up int ed = last[x], dr; while(ed != -1) { dr = other[ed]; if(dr != fa) Dfs(dr, x); ed = pre[ed]; } } int Get_LCA(int x, int y) { if(dep[x] < dep[y]) swap(x, y); int d = dep[x] - dep[y]; for(int i = 0; i <= 20; i++) //是dep[x]和dep[y]的深度一样 if(d & (1 << i)) x = up[x][i]; if(x == y) return x; for(int i = 20; i >= 0; i--) { if(up[x][i] != up[y][i]) { x = up[x][i]; y = up[y][i]; } } return up[x][0]; //为什么return这个?想一下就应该知道了 } int get_dist(int x, int y) { int u = Get_LCA(x, y); return dep[x] + dep[y] - 2 * dep[u]; } int main() { while(scanf("%d %d", &n, &q) != EOF) { all = -1; memset(last, -1, sizeof(last)); for(int i = 2; i <= n; i++) { int p; scanf("%d", &p); build(p, i); build(i, p); } dep[1] = 1; Dfs(1, 0); for(int i = 1; i <= q; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); int ans = 0; int dis_ab = get_dist(a, b); int dis_ac = get_dist(a, c); int dis_bc = get_dist(b, c); //画个图出来稍微观察一下就能得到这个公式 int na = (dis_ac + dis_ab - dis_bc) / 2; int nb = (dis_ab + dis_bc - dis_ac) / 2; int nc = (dis_ac + dis_bc - dis_ab) / 2; ans = max(na + 1, max(nb + 1, nc + 1)); printf("%d\n", ans); } memset(pre, 0, sizeof(pre)); memset(other, 0, sizeof(other)); memset(dep, 0, sizeof(dep)); memset(up, 0, sizeof(up)); } return 0; }