给你一颗无根树。每条边的路径长是1。
每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。
看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据,发现求的点一定在其中两个点的LCA。
那么就好了。每次求出3个LCA。然后枚举。算出距离和。
介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。
如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char buf[21000000],*pt=buf,*o=buf; int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0}; int lg[500005],a[500005][20],n,m,tot=1; inline int getint(){ int r=0; while(*pt<48||*pt>57)pt++; while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r; }inline void print(int x){ char str[11],*p=str; if(!x)*o++=48; else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;} }inline void ae(int a,int b){ p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++; }inline void pre(){ int s=0,e=1; q[0]=1; d[1]=1; v[1]=1; while(s<e){ for(int i=h[q[s++]];i;i=n1[i]) if(!v[p[i]]) v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1]; }for(int j=1;j<20;j++) for(int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1]; }inline int lca(int u,int v){ if(d[u]>d[v]){ u^=v; v^=u; u^=v;} int k=d[v]-d[u],j=0; while(k){ if(k&1)v=a[v][j]; j++; k>>=1;} if(u==v)return u; for(int i=lg[d[u]-1];~i;i--) if(a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i]; return a[u][0]; }int main(){ fread(pt,1,21000000,stdin); n=getint();m=getint(); for(int i=0;(1<<i)<=n;i++) for(int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i; int u,v,w,a1,a2,a3,a4,a5,An1,An2; for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); pre(); for(int i=1;i<=m;i++){ u=getint(),v=getint(),w=getint(); a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w]; An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1); if((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2; if((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3; print(An1);*o++=' ';print(An2);*o++='\n'; }return fwrite(buf,1,o-buf,stdout),0; }