有询问$a,b,c$,求a到c路径上,同时是a到b路径的点的个数。其中询问中的a,b,c可任意选择作为起点或终点,求一组询问中最大值。

LCA用于计算树上点对间距离,对于一组询问求深度最大的点作为起点,再在其中找最大距离的点就可以了

/** @Date    : 2017-08-04 20:17:42
* @FileName: D LCA.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; int n, q;
vectoredg[N];
int deg[N];
int fa[N][20]; void init()
{
for(int j = 1; (1 << j) <= n; j++)
{
for(int i = 1; i <= n; i++)
{
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
} void dfs(int x, int pre, int dep)
{
deg[x] = dep;
for(auto i: edg[x])
{
if(i == pre)
continue;
fa[i][0] = x;
dfs(i, x, dep + 1);
}
} int lca(int a, int b)
{
if(deg[a] > deg[b])
swap(a, b);
int det = deg[b] - deg[a];
for(int i = 0; (1 << i) <= det; i++)
{
if((1 << i) & det)
b = fa[b][i];
}
if(a == b)
return a;
for(int i = 19; i >= 0; i--)
{
if(fa[a][i] == fa[b][i])
continue;
a = fa[a][i];
b = fa[b][i];
}
return fa[a][0];
} int dis(int a, int b)
{
return deg[a] + deg[b] - 2 * deg[lca(a, b)];
} int main()
{
while(cin >> n >> q)
{
for(int i = 2; i <= n; i++)
{
int x;
scanf("%d", &x);
edg[x].PB(i);
edg[i].PB(x);
}
dfs(1, -1, 0);
init();
while(q--)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int f1 = lca(x, y);
int f2 = lca(x, z);
int f3 = lca(y, z);
if(deg[f1] < deg[f2]) f1 = f2;
if(deg[f1] < deg[f3]) f1 = f3;
int ans = max(dis(f1, x), max(dis(f1, y), dis(f1, z)));
printf("%d\n", ans + 1);
}
}
return 0;
}
05-18 09:25
查看更多