首页 > 代码库 > BZOJ 1832 聚会
BZOJ 1832 聚会
不想写。。。直接粘过来。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 501000#define LOGN 20#define inf 0x3f3f3f3fusing namespace std;struct KSD{ int v,next;}e[N<<1];int head[N],cnt;inline void add(int u,int v){ cnt++; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt;}int n,m;int fa[N][LOGN],deep[N];void dfs(int x,int p){ int i,v; deep[x]=deep[p]+1; for(i=head[x];i;i=e[i].next) { v=e[i].v; if(v==p)continue; fa[v][0]=x; dfs(v,x); } return ;}inline void array(){ int i,j; for(j=1;j<LOGN;j++) for(i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];}int lcansx,lcansy;inline int getlca(int x,int y){ if(deep[x]<deep[y])swap(x,y); int i,j,k; lcansx=lcansy=0; for(i=LOGN-1;i>=0;i--) if(deep[fa[x][i]]>=deep[y])x=fa[x][i],lcansx+=(1<<i); if(x==y)return x; for(i=LOGN-1;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i],lcansy+=(1<<i); lcansy+=1,lcansx+=lcansy; return fa[x][0];}int main(){// freopen("test.in","r",stdin); int i,ans,id; int a,b,c; scanf("%d%d",&n,&m); for(i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } dfs(1,0); array(); while(m--) { scanf("%d%d%d",&a,&b,&c); int lca=getlca(a,b),temp=lcansx+lcansy; getlca(lca,c); temp+=lcansx+lcansy; ans=temp,id=lca; lca=getlca(a,c),temp=lcansx+lcansy; getlca(lca,b); temp+=lcansx+lcansy; if(ans>temp)ans=temp,id=lca; lca=getlca(b,c),temp=lcansx+lcansy; getlca(lca,a); temp+=lcansx+lcansy; if(ans>temp)ans=temp,id=lca; printf("%d %d\n",id,ans); } return 0;}
BZOJ 1832 聚会
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。