1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//给一棵树，求两个节点的LCA
#include<iostream>
#include<map>
#include<cstring>
#define pii pair<int, int>
using namespace std;
const int N = 120005;
int fa[N];
map<pii, int> Q;
map<pii, int> Ans;
bool vis[N];
int root;
int n,q;
struct Edge{
int u, v, nxt, ans;
}e[N * 2], ans[N*6];
int cnt, cntq;
int h[N], hq[N];
void init(){
memset(h, -1, sizeof(h));
memset(hq, -1, sizeof(hq));
cnt = cntq = 0;
}
void add(int u, int v){
e[cnt].v = v;
e[cnt].nxt = h[u];
h[u] = cnt++;
}
void addq(int u, int v){
ans[cntq].ans = 0;
ans[cntq].v = v;
ans[cntq].nxt = hq[u];
hq[u] = cntq++;
}
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void tarjan(int u,int pre){
int v;
fa[u] = u;
for(int k = h[u]; ~k; k = e[k].nxt){//后序遍历
v = e[k].v;
if (v==pre)
continue;
tarjan(v,u);
fa[v] = u;//并入并查集
}
vis[u] = true;//后序遍历
for(int k = hq[u]; ~k; k = ans[k].nxt){//查找LCA
v = ans[k].v;
if(vis[v]){
Ans[make_pair(u,v)] = Ans[make_pair(v,u)] = find(v);//此处为u，v的LCA
}
}
}
int t;
const int maxn = 120000;
int deep[maxn];
int a[maxn],b[maxn],c[maxn];
void dfs(int u,int pos,int pre)
{
deep[u] = pos;
for (int i = h[u] ; i != -1 ; i = e[i].nxt)
{
int v = e[i].v;
if (v==pre)
continue;
dfs(v,pos+1,u);
}
}
int main()
{
memset(h,-1,sizeof(h));
memset(hq,-1,sizeof(hq));
scanf("%d%d",&n,&q);
for (int i = 2 ; i <= n ; i ++)
{
scanf("%d",&t);
add(i,t);
add(t,i);
}
dfs(1,0,1);
memset(vis, false, sizeof(vis));
for (int i =1 ; i <= q ; i ++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
addq(a[i],b[i]);
addq(b[i],a[i]);
addq(b[i],c[i]);
addq(c[i],b[i]);
addq(a[i],c[i]);
addq(c[i],a[i]);
}
tarjan(1,1);
for (int i = 1; i <= q ; i ++)
{
int lab = deep[a[i]]+deep[b[i]]-2*deep[Ans[pii(a[i],b[i])]];
int lac = deep[a[i]]+deep[c[i]]-2*deep[Ans[pii(a[i],c[i])]];
int lbc = deep[b[i]]+deep[c[i]]-2*deep[Ans[pii(b[i],c[i])]];
int p = (lab+lac+lbc)/2;
int x = p - lab;
int y = p - lac;
int z = p - lbc;
//printf("lab %d lac %d lbc %d\n",lab,lac,lbc);
//printf("%d %d %d\n",x,y,z);
printf("%d\n",max(x,max(y,z))+1);
//printf("ab %d ac %d bc %d \n",Ans[pii(a[i],b[i])],Ans[pii(a[i],c[i])],Ans[pii(c[i],b[i])]);
}
return 0;
}
|
