首页 > 代码库 > BZOJ——1787: [Ahoi2008]Meet 紧急集合
BZOJ——1787: [Ahoi2008]Meet 紧急集合
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\n",anspoint,anssum);64 }65 return 0;66 }
BZOJ——1787: [Ahoi2008]Meet 紧急集合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。