http://www.lydsy.com/JudgeOnline/problem.php?id=1787
题目描述
输入
输出
样例输入
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
样例输出
5 2
2 5
4 1
6 0
提示
易发现：三个点两两求出LCA，一定至少有两个LCA相等
若只有两个相等，那聚集点就是剩下的LCA
若三个相等，那聚集点就是LCA
1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4 5 using namespace std; 6 7 const int N(1e5*5+15); 8 vector<int>vec[N]; 9 int n,m,x,y,z; 10 int anspoint,anssum; 11 int deep[N],dad[N],size[N],top[N]; 12 13 void DFS(int x) 14 { 15 size[x]=1; deep[x]=deep[dad[x]]+1; 16 for(int i=0;i<vec[x].size();i++) 17 if(dad[x]!=vec[x][i]) 18 { 19 dad[vec[x][i]]=x; 20 DFS(vec[x][i]); 21 size[x]+=size[vec[x][i]]; 22 } 23 } 24 25 void DFS_(int x) 26 { 27 int t=0; if(!top[x]) top[x]=x; 28 for(int i=0;i<vec[x].size();i++) 29 if(vec[x][i]!=dad[x]&&size[t]<size[vec[x][i]]) t=vec[x][i]; 30 if(t) top[t]=top[x],DFS_(t); 31 for(int i=0;i<vec[x].size();i++) 32 if(vec[x][i]!=dad[x]&&t!=vec[x][i]) DFS_(vec[x][i]); 33 } 34 35 int LCA(int x,int y) 36 { 37 while(top[x]!=top[y]) 38 { 39 if(deep[top[x]]<deep[top[y]]) swap(x,y); 40 x=dad[top[x]]; 41 } 42 if(deep[x]>deep[y]) swap(x,y); 43 return x; 44 } 45 46 int main() 47 { 48 scanf("%d%d",&n,&m); 49 for(int i=1;i<n;i++) 50 { 51 scanf("%d%d",&x,&y); 52 vec[x].push_back(y); 53 vec[y].push_back(x); 54 } 55 DFS(1); DFS_(1); 56 for(;m;m--) 57 { 58 scanf("%d%d%d",&x,&y,&z); 59 anspoint=LCA(x,y)^LCA(x,z)^LCA(y,z); 60 anssum =deep[x]+deep[anspoint]-(deep[LCA(x,anspoint)]<<1); 61 anssum+=deep[y]+deep[anspoint]-(deep[LCA(y,anspoint)]<<1); 62 anssum+=deep[z]+deep[anspoint]-(deep[LCA(z,anspoint)]<<1); 63 printf("%d %d ",anspoint,anssum); 64 } 65 return 0; 66 }