bzoj 1832: [AHOI2008]聚会

良心题2333

三个点两两求一遍就行,最小肯定是在某2个点的lca处,(肯定让第三个人去找2个人,不能让2个人一起去找第三个人233)

 #include<bits/stdc++.h>
#define N 500005
#define M 10000005
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
struct node{
int to,next;
}e[N<<];
int head[N],cnt;
int fa[N][],deep[N],n,m;
void insert(int x, int y){e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;}
void dfs(int x)
{
for (int i=; i<=; i++)
if (deep[x]>=(<<i))
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for (int i=head[x];i;i=e[i].next)
{
if (e[i].to==fa[x][]) continue;
fa[e[i].to][]=x;
deep[e[i].to]=deep[x]+;
dfs(e[i].to);
}
}
int lca(int x, int y)
{
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=; (<<i)<=t ; i++)
if (t&(<<i)) x=fa[x][i];
for (int i=; i>=; i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if (x==y) return x;
return fa[x][];
}
int lca_cost(int x, int y)
{
int sum=;
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for (int i=; (<<i)<=t ; i++)
if (t&(<<i)) x=fa[x][i],sum+=(<<i);
for (int i=; i>=; i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i],sum+=(<<i)*;
if (x==y) return sum;
return sum+;
}
int main()
{
n=ra(); m=ra();
for (int i=; i<n; i++)
{
int x=ra(),y=ra();
insert(x,y); insert(y,x);
}
dfs();
for (int i=; i<=m; i++)
{
int x=ra(),y=ra(),z=ra();
int ans1=lca_cost(x,y)+lca_cost(lca(x,y),z);
int ans2=lca_cost(x,z)+lca_cost(lca(x,z),y);
int ans3=lca_cost(y,z)+lca_cost(lca(y,z),x);
int ans=min(min(ans1,ans2),ans3);
if (ans==ans1) printf("%d ",lca(x,y));
else if (ans==ans2) printf("%d ",lca(x,z));
else if (ans==ans3) printf("%d ",lca(y,z));
printf("%d\n",ans);
}
}
上一篇:SqlServer和Oracle中一些常用的sql语句6 存储过程


下一篇:LeetCode-2AddTwoNumbers(C#)