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
/* ***********************************************
Author :111qqz
Created Time :2017年07月30日 星期日 15时12分34秒
File Name :D.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,q;
8vector < pi > edge[N];
9int in[N];
10int E[2*N],R[2*N],dis[N],depth[2*N];
11int p;
12int dp[2*N][20];
13void dfs( int u,int dep,int d,int pre)
14{
1 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl;
2 p++;
3 E[p] = u;
4 depth[p] = dep;
5 R[u] = p ;
6 dis[u] = d;
1 int siz = edge[u].size();
2 for ( int i = 0 ; i < siz ; i++)
3 {
4 int v = edge[u][i].fst;
5 if (v==pre) continue;
6 dfs(v,dep+1,d+edge[u][i].sec,u);
1 p++;
2 E[p] = u;
3 depth[p] = dep;
4 }
5}
1int _min( int l,int r)
2{
3 if (depth[l]<depth[r]) return l;
4 return r;
5}
6void rmq_init()
7{
8 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i;
1 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++)
2 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++)
3 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
4}
1int rmq_min( int l,int r)
2{
3 if (l>r) swap(l,r);
4 int k = 0 ;
5 while (1<<(k+1)<=r-l+1) k++;
6 return _min(dp[l][k],dp[r-(1<<k)+1][k]);
7}
8int D(int u,int v) //计算u,v点的距离
9{
10 int LCA = E[rmq_min(R[u],R[v])];
11 int res = dis[u] + dis[v] - 2*dis[LCA];
12 return res;
13}
14/*
15int solve( int a,int b,int c) //a->c,b->c
16{
17 int LCA = E[rmq_min(R[a],R[b])];
18 int res = inf; //check分支
19 printf("[%d %d] %d\n",a,b,LCA);
20 printf("dis[c]:%i dis[LCA]:%i\n",dis[c],dis[LCA]);
21 if (dis[LCA]>dis[c])
22 {
23 int LCA3 = E[rmq_min(R[c],R[LCA])];
1// if (dis[c]+D(c,LCA)==dis[LCA])
2// res = dis[LCA]-dis[c]+1;
3// else
4 if (D(c,LCA3)+D(LCA3,LCA)==D(c,LCA))
5 res = D(c,LCA)+1;
6 }
7 if (dis[LCA]==dis[c])
8 {
1 if (LCA==c) res = 1;
2 else res = D(c,LCA) + 1; //直接错把LCA固定在根了。。
3 }
4 if (dis[LCA]<dis[c])
5 {
6 int LCA1 = E[rmq_min(R[b],R[c])];
7 int LCA2 = E[rmq_min(R[a],R[c])];
8 printf("LCA1:%d LCA2:%d\n",LCA1,LCA2);
9 if (D(b,c)==D(b,a)+D(a,c))
10 {
11 res =D(a,c)+1;
12// cout<<"1"<<endl;
13 }
14 else
15 if (D(a,c)==D(a,b)+D(b,c))
16 {
17 res = D(b,c)+1;
18 // cout<<"2"<<endl;
19 }
20 else
21 if (D(LCA,a)==D(LCA,c) + D(c,a)||D(LCA,b)==D(LCA,c)+D(c,b))
22 {
23 res = 1; //只在c点汇合
24 // cout<<"3:"<<endl;
25 }
26 else
27 if (D(c,LCA1)+D(LCA1,b)==D(c,b)&&D(c,LCA)+D(LCA,b)!=D(c,b)) //在靠近b的另外分支
28 {
29 if (D(LCA,LCA1)==dis[c]-dis[LCA1])
30 res = D(c,LCA1)+1;
31 else res = D(c,LCA)+1;
32 cout<<"4:"<<endl;
33 }
34 else
35 if (D(c,LCA2)+D(LCA2,a)==D(c,a)&&D(c,LCA)+D(LCA,a)!=D(c,a))
36 {
37 if (D(LCA,LCA2)==dis[c]-dis[LCA])
38 res = D(c,LCA2) + 1;
39 else res = D(c,LCA)+1;
40 cout<<"5:"<<endl;
41 }
42 }
43 return res;
44}
45 */
46int max_dep3(int a,int b,int c)
47{
48 int ret = 0;
49 int mx = -1;
50 if (dis[a]>mx)
51 {
52 mx = dis[a];
53 ret = a;
54 }
55 if (dis[b]>mx)
56 {
57 mx = dis[b];
58 ret = b;
59 }
60 if (dis[c]>mx)
61 {
62 mx = dis[c];
63 ret = c;
64 }
65 return ret;
66}
67int max3( int a,int b, int c)
68{
69 int mx = -1;
70 mx = max(a,b);
71 mx = max(mx,c);
72 return mx;
73}
1int main()
2{
3#ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5#endif
1 ms(in,0);
2 scanf("%d %d",&n,&q);
3 for ( int i = 2 ; i <= n ; i++)
4 {
5 int x;
6 scanf("%d",&x);
7 edge[i].push_back(make_pair(x,1));
8 edge[x].push_back(make_pair(i,1));
9 }
10 p = 0 ;
11 dfs(1,0,0,-1);
12 rmq_init();
1 while (q--)
2 {
3 int a,b,c;
4 scanf("%d%d%d",&a,&b,&c);
5 vector<int>ret;
6 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])]);
7 int ans = max3(D(LCA,a),D(LCA,b),D(LCA,c))+1;
8 printf("%d\n",ans);
9// printf("%d\n",solve(a,b,c));
10 }
11#ifndef ONLINE_JUDGE
12 fclose(stdin);
13#endif
14 return 0;
15}