注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【BZOJ1787】【乱搞题】[Ahoi2008]Meet 紧急集合  

2014-05-02 08:57:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1787 [Ahoi2008]Meet 紧急集合

乱搞题

可以看出花费的最少金币数一定是联通三点的路径长度,这个可以每次logn得到

然后找集合地点
联通三点的路径要么是一条链要么是Y字形
如果是一条链就在中间的人上,如果是Y形就在Y的中心点上
分类讨论一下所有情况(或者证明一下)可以得到这个集合点必在某两点的LCA上(分类讨论的时候注意树根的不同位置),这样这个集合点就剩下三个可能了,枚举一下答案就过了
因为是水题所以1A
【BZOJ1787】【乱搞题】[Ahoi2008]Meet 紧急集合 - 时光机 - 时光机TimeMachine
 但是我的效率不知道为啥低得可怕……

/*
代价=三点间的联通路径长度,(容斥原理)两两之间距离之和除以二
集合地点必定在某两点的 LCA上,枚举一下就好了

*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
using namespace std;
const int N = 5*100000+100;
const int LOGN = 21;
int n,m,logn;
int deep[N],anc[N][LOGN];
queue<int>dui;
struct list{
int d;
list *next;
list(){next=NULL;}
void push(int a){
list *l;
l=new list();
l->next=next;next=l;
l->d=a;
}
}map[N];
//为了防止爆栈用bfs
int Anc(int x,int k){
if(k<0) return -1;
if(1+(1<<k) > deep[x]) return -1;//?
if(anc[x][k]==-1)anc[x][k]=Anc(Anc(x,k-1),k-1);
return anc[x][k];
}
void swap(int &a,int &b){int c=a;a=b;b=c;}
int lca(int a,int b){
if(deep[a]<deep[b]) swap(a,b);
int fa,fb;
for(int k=logn;k>=0;k--)
if((fa=Anc(a,k))!=-1&&deep[fa]>=deep[b])
if(deep[a=fa]==deep[b]) break;
if(a==b) return a;
for(int k=logn;k>=0;k--)
if(((fa=Anc(a,k))!=-1)&&((fb=Anc(b,k))!=fa))
a=fa,b=fb;
return anc[a][0];
}
int bfs(){
dui.push(1);deep[1]=1;anc[1][0]=0;
while(!dui.empty()){
int now=dui.front();dui.pop();
for(list *i=map[now].next;i!=NULL;i=i->next){
if(anc[i->d][0]==-1){
anc[i->d][0]=now;
deep[i->d]=deep[now]+1;
dui.push(i->d);
}
}
}
}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc=='\n'||cc==' '||cc=='\r')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
int dis(int a,int b){return deep[a]+deep[b]-deep[lca(a,b)]*2;}
int main(){
memset(anc,-1,sizeof(anc));
int i,j,a,b,c;
n=scan();m=scan();
logn=(int)(log(n)/log(2))+1;
for(i=1;i<n;i++){
a=scan();b=scan();
map[a].push(b);
map[b].push(a);
}
bfs();
int lcaab,lcabc,lcaac,ans1,ans2;
for(i=1;i<=m;i++){
a=scan();b=scan();c=scan();
lcaab=lca(a,b);
lcabc=lca(b,c);
lcaac=lca(a,c);
ans1=deep[a]+deep[b]+deep[c]-(deep[lcaab]+deep[lcaac]+deep[lcabc]);
if(dis(a,b)+dis(lcaab,c)==ans1)ans2=lcaab;
if(dis(b,c)+dis(lcabc,a)==ans1)ans2=lcabc;
if(dis(a,c)+dis(lcaac,b)==ans1)ans2=lcaac;
printf("%d %d\n",ans2,ans1);
}
return 0;
}


  评论这张
 
阅读(49)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017