首页 > 代码库 > 【块状树】【LCA】bzoj1787 [Ahoi2008]Meet 紧急集合

【块状树】【LCA】bzoj1787 [Ahoi2008]Meet 紧急集合

2024-07-30 00:05:11   221人阅读

分块LCA什么的，意外地快呢……

就是对询问的3个点两两求LCA，若其中两组LCA相等，则答案为第三者。

然后用深度减一减什么的就求出距离了。

 1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define maxn 500001 6 struct Graph 7 {int v[maxn<<1],first[maxn<<1],next[maxn<<1],w[maxn<<1],en; 8 void AddEdge(const int &a,const int &b) 9 {v[++en]=b;next[en]=first[a];first[a]=en;}}G;10 int dep[maxn],fa[maxn],top[maxn],siz[maxn],x,y,z,sz,n,m;11 int Abs(const int &x){return x<0 ? (-x) : x;}12 int Res,Num;char C,CH[12];13 inline int R()14 {15     Res=0;C=‘*‘;16     while(C<‘0‘||C>‘9‘)C=getchar();17     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}18     return Res;19 }20 inline void P(long long x)21 {22     Num=0;if(!x){putchar(‘0‘);return;}23     while(x>0)CH[++Num]=x%10,x/=10;24     while(Num)putchar(CH[Num--]+48);25 }26 void makeblock(int cur)27 {28     for(int i=G.first[cur];i;i=G.next[i])29       if(G.v[i]!=fa[cur])30         {31           dep[G.v[i]]=dep[cur]+1;32           fa[G.v[i]]=cur;33           if(siz[top[cur]]<sz)34             {35               siz[top[cur]]++;36               top[G.v[i]]=top[cur];37             }38           makeblock(G.v[i]);39         }40 }41 inline int QLCA(int u,int v)42 {43     while(u!=v)44       {45         if(top[u]==top[v])46           {47             if(dep[u]<dep[v]) swap(u,v);48             u=fa[u];49           }50         else51           {52             if(dep[top[u]]<dep[top[v]]) swap(u,v);53             u=fa[top[u]];54           }55       }56     return u;57 }58 int main()59 {60     n=R();m=R();61     for(int i=1;i<n;i++)62       {63         x=R();y=R();64         G.AddEdge(x,y);65         G.AddEdge(y,x);66       }67     for(int i=1;i<=n;i++) {top[i]=i; siz[i]=1;}68     sz=sqrt((double)n*5.0); makeblock(1);69     for(;m>0;m--)70       {71         x=R();y=R();z=R();72         int f1=QLCA(x,y),f2=QLCA(x,z),f3=QLCA(y,z);73         if(f1==f2)74           {75             int f4=QLCA(x,f3); P(f3); putchar(‘ ‘);76             P(Abs(dep[f3]-dep[y])+Abs(dep[f3]-dep[z])77             +Abs(dep[f4]-dep[x])+Abs(dep[f4]-dep[f3])); puts("");78           }79         else if(f1==f3)80           {81             int f4=QLCA(y,f2); P(f2); putchar(‘ ‘);82             P(Abs(dep[f2]-dep[x])+Abs(dep[f2]-dep[z])83             +Abs(dep[f4]-dep[y])+Abs(dep[f4]-dep[f2])); puts("");84           }85         else86           {87             int f4=QLCA(z,f1); P(f1); putchar(‘ ‘);88             P(Abs(dep[f1]-dep[x])+Abs(dep[f1]-dep[y])89             +Abs(dep[f4]-dep[z])+Abs(dep[f4]-dep[f1])); puts("");90           }91       }92     return 0;93 }

 

【块状树】【LCA】bzoj1787 [Ahoi2008]Meet 紧急集合


联系
我们