BZOJ 1832、1787 洛谷 4281 [AHOI2008]紧急集合

BZOJ 1832、1787 洛谷 4281 [AHOI2008]紧急集合

【题解】

  题目要求找到一个集合点,使3个给定的点到这个集合点的距离和最小,输出集合点的编号以及距离。

  设三个点为A,B,C;那么我们可以得到Dis=dep[A]+dep[B]+dep[C]-dep[Lca]-dep[Lca2]*2;其中Lca是A,B的最近公共祖先;Lca2是Lca与C的最近公共祖先。那么为了使Dis最大,必须使dep[Lca]+dep[Lca2]*2最大。那么我们只需找出A,B,C两两之间Lca中Dep最大的作为集合点就可以了。

  

#include<cstdio>
#include<algorithm>
#define N 500010
#define rg register
using namespace std;
int n,m,tot,last[N],dep[N],son[N],size[N],fa[N],top[N];
struct edge{
int to,pre;
}e[N<<1];
inline int read(){
int k=0,f=1; char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
inline void add(int x,int y){
e[++tot]=(edge){y,last[x]}; last[x]=tot;
}
void dfs1(int x){
size[x]=1; dep[x]=dep[fa[x]]+1;
for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa[x]){
fa[to]=x; dfs1(to);
size[x]+=size[to];
if(size[to]>size[son[x]]) son[x]=to;
}
}
void dfs2(int x,int tp){
top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(rg int i=last[x],to;i;i=e[i].pre)
if((to=e[i].to)!=fa[x]&&to!=son[x]) dfs2(to,to);
}
inline int lca(int x,int y){
int f1=top[x],f2=top[y];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
x=fa[f1]; f1=top[x];
}
return dep[x]<dep[y]?x:y;
}
int main(){
n=read(); m=read();
for(rg int i=1;i<n;i++){
int u=read(),v=read();
add(u,v); add(v,u);
}
dfs1(1); dfs2(1,1);
// for(rg int i=1;i<=m;i++) printf("%d\n",lca(read(),read()));
for(rg int i=1;i<=m;i++){
int a=read(),b=read(),c=read();
int l1=lca(a,b),l2=lca(a,c),l3=lca(b,c);
if(dep[l1]>=dep[l2]&&dep[l1]>=dep[l3]){
printf("%d ",l1);
printf("%d\n",dep[a]+dep[b]+dep[c]-dep[l1]-(dep[lca(l1,c)]<<1));
continue;
}
if(dep[l2]>=dep[l1]&&dep[l2]>=dep[l3]){
printf("%d ",l2);
printf("%d\n",dep[a]+dep[b]+dep[c]-dep[l2]-(dep[lca(l2,b)]<<1));
continue;
}
if(dep[l3]>=dep[l1]&&dep[l3]>=dep[l2]){
printf("%d ",l3);
printf("%d\n",dep[a]+dep[b]+dep[c]-dep[l3]-(dep[lca(l3,a)]<<1));
continue;
}
}
return 0;
}

  

上一篇:.NET混淆器和压缩器Dotfuscator介绍


下一篇:Sublime Text 3安装SFTP插件