codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)
题意：
给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。
思路：
LCA还是一下就能想到的，rmq+dfs在线求。
然后我开始分情况讨论，讨论了一年也没讨论完，哭哭
结论是：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。
所以我的问题在于，没有试图往一般性的方向考虑，以为讨论一下就可以了…
这大概就是所谓的猜结论？
感性的理解的话，LCA越深，意味着另一个点到LCA的距离越远，也就是相交的路径越长
但是我的话，估计还是很难在短短不到一个小时内得出这样一般性的结论orz…
这大概就是数学方面的天赋差距把…T T
1/* ***********************************************
2Author :111qqz
3Created Time :2017年07月30日 星期日 15时12分34秒
4File Name :D.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,q;
35vector < pi > edge[N];
36int in[N];
37int E[2*N],R[2*N],dis[N],depth[2*N];
38int p;
39int dp[2*N][20];
40void dfs( int u,int dep,int d,int pre)
41{
42
43 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl;
44 p++;
45 E[p] = u;
46 depth[p] = dep;
47 R[u] = p ;
48 dis[u] = d;
49
50
51 int siz = edge[u].size();
52 for ( int i = 0 ; i < siz ; i++)
53 {
54 int v = edge[u][i].fst;
55 if (v==pre) continue;
56 dfs(v,dep+1,d+edge[u][i].sec,u);
57
58 p++;
59 E[p] = u;
60 depth[p] = dep;
61 }
62}
63
64
65
66int _min( int l,int r)
67{
68 if (depth[l]<depth[r]) return l;
69 return r;
70}
71void rmq_init()
72{
73 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
74
75 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
76 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
77 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
78}
79
80int rmq_min( int l,int r)
81{
82 if (l>r) swap(l,r);
83 int k = 0 ;
84 while (1<<(k+1)<=r-l+1) k++;
85 return _min(dp[l][k],dp[r-(1<<k)+1][k]);
86}
87int D(int u,int v) //计算u,v点的距离
88{
89 int LCA = E[rmq_min(R[u],R[v])];
90 int res = dis[u] + dis[v] - 2*dis[LCA];
91 return res;
92}
93/*
94int solve( int a,int b,int c) //a->c,b->c
95{
96 int LCA = E[rmq_min(R[a],R[b])];
97 int res = inf; //check分支
98 printf("[%d %d] %d\n",a,b,LCA);
99 printf("dis[c]:%i dis[LCA]:%i\n",dis[c],dis[LCA]);
100 if (dis[LCA]>dis[c])
101 {
102 int LCA3 = E[rmq_min(R[c],R[LCA])];
103
104// if (dis[c]+D(c,LCA)==dis[LCA])
105// res = dis[LCA]-dis[c]+1;
106// else
107 if (D(c,LCA3)+D(LCA3,LCA)==D(c,LCA))
108 res = D(c,LCA)+1;
109 }
110 if (dis[LCA]==dis[c])
111 {
112
113 if (LCA==c) res = 1;
114 else res = D(c,LCA) + 1; //直接错把LCA固定在根了。。
115 }
116 if (dis[LCA]<dis[c])
117 {
118 int LCA1 = E[rmq_min(R[b],R[c])];
119 int LCA2 = E[rmq_min(R[a],R[c])];
120 printf("LCA1:%d LCA2:%d\n",LCA1,LCA2);
121 if (D(b,c)==D(b,a)+D(a,c))
122 {
123 res =D(a,c)+1;
124// cout<<"1"<<endl;
125 }
126 else
127 if (D(a,c)==D(a,b)+D(b,c))
128 {
129 res = D(b,c)+1;
130 // cout<<"2"<<endl;
131 }
132 else
133 if (D(LCA,a)==D(LCA,c) + D(c,a)||D(LCA,b)==D(LCA,c)+D(c,b))
134 {
135 res = 1; //只在c点汇合
136 // cout<<"3:"<<endl;
137 }
138 else
139 if (D(c,LCA1)+D(LCA1,b)==D(c,b)&&D(c,LCA)+D(LCA,b)!=D(c,b)) //在靠近b的另外分支
140 {
141 if (D(LCA,LCA1)==dis[c]-dis[LCA1])
142 res = D(c,LCA1)+1;
143 else res = D(c,LCA)+1;
144 cout<<"4:"<<endl;
145 }
146 else
147 if (D(c,LCA2)+D(LCA2,a)==D(c,a)&&D(c,LCA)+D(LCA,a)!=D(c,a))
148 {
149 if (D(LCA,LCA2)==dis[c]-dis[LCA])
150 res = D(c,LCA2) + 1;
151 else res = D(c,LCA)+1;
152 cout<<"5:"<<endl;
153 }
154 }
155 return res;
156}
157 */
158int max_dep3(int a,int b,int c)
159{
160 int ret = 0;
161 int mx = -1;
162 if (dis[a]>mx)
163 {
164 mx = dis[a];
165 ret = a;
166 }
167 if (dis[b]>mx)
168 {
169 mx = dis[b];
170 ret = b;
171 }
172 if (dis[c]>mx)
173 {
174 mx = dis[c];
175 ret = c;
176 }
177 return ret;
178}
179int max3( int a,int b, int c)
180{
181 int mx = -1;
182 mx = max(a,b);
183 mx = max(mx,c);
184 return mx;
185}
186
187int main()
188{
189#ifndef ONLINE_JUDGE
190 freopen("./in.txt","r",stdin);
191#endif
192
193 ms(in,0);
194 scanf("%d %d",&n,&q);
195 for ( int i = 2 ; i <= n ; i++)
196 {
197 int x;
198 scanf("%d",&x);
199 edge[i].push_back(make_pair(x,1));
200 edge[x].push_back(make_pair(i,1));
201 }
202 p = 0 ;
203 dfs(1,0,0,-1);
204 rmq_init();
205
206 while (q--)
207 {
208 int a,b,c;
209 scanf("%d%d%d",&a,&b,&c);
210 vector<int>ret;
211 int LCA = max_dep3(E[rmq_min(R[a],R[b])],E[rmq_min(R[b],R[c])],E[rmq_min(R[a],R[c])]);
212 int ans = max3(D(LCA,a),D(LCA,b),D(LCA,c))+1;
213 printf("%d\n",ans);
214// printf("%d\n",solve(a,b,c));
215 }
216#ifndef ONLINE_JUDGE
217 fclose(stdin);
218#endif
219 return 0;
220}