[BZOJ 1787]紧急集合
转载请注明出处:http://danihao123.is-programmer.com/
这个题需要一些脑洞。
给出任意三点,如果我们两两求LCA,肯定有两组相同,剩下那一组就是最优集合点了。为啥?画图理解一下吧……
代码:
/************************************************************** Problem: 1787 User: danihao123 Language: C++ Result: Accepted Time:4068 ms Memory:80900 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define REP(i,n) for(i=0;i<(n);i++) #define REP_B(i,n) for(i=1;i<=(n);i++) #define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i]) #define TWO_POW(n) (1<<(n)) const int maxn=500001,maxm=1000001; int first[maxn]; int next[maxm],to[maxm],dist[maxm]; int graph_cnt=0; inline void Add_Edge(int u,int v,int d){ graph_cnt++; next[graph_cnt]=first[u]; first[u]=graph_cnt; to[graph_cnt]=v; dist[graph_cnt]=d; } int d[maxn]; int dep[maxn]; int anc[maxn][32]; void dfs(int x,int father,int depth,int dis){ d[x]=dis; anc[x][0]=father; dep[x]=depth; int i; GRAPH_REP(i,x){ if(to[i]!=father) dfs(to[i],x,depth+1,dis+dist[i]); } } int n; inline void InitLCA(){ register int i,j; for(j=1;TWO_POW(j)<n;j++){ REP_B(i,n){ if(anc[i][j-1]!=-1){ anc[i][j]=anc[anc[i][j-1]][j-1]; } } } } int QueryLCA(int x,int y){ register int j,log; if(dep[x]<dep[y]) swap(x,y); for(log=1;TWO_POW(log)<=dep[x];log++); log--; for(j=log;j>=0;j--) if(dep[x]-TWO_POW(j)>=dep[y]) x=anc[x][j]; if(x==y) return y; for(j=log;j>=0;j--){ if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){ x=anc[x][j]; y=anc[y][j]; } } return anc[x][0]; } inline int make_dis(int x,int y){ return d[x]+d[y]-2*d[QueryLCA(x,y)]; } int main(){ int u,v,D; int x,y,z,QinDing; int m; register int i,j; scanf("%d%d",&n,&m); REP(i,n-1){ scanf("%d%d",&u,&v); Add_Edge(u,v,1); Add_Edge(v,u,1); } memset(anc,-1,sizeof(anc)); dfs(1,-1,0,0); InitLCA(); REP(i,m){ scanf("%d%d%d",&u,&v,&D); x=QueryLCA(u,v); y=QueryLCA(u,D); z=QueryLCA(v,D); if(x==y){ QinDing=z; }else{ if(x==z){ QinDing=y; }else{ QinDing=x; } } printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D)); } return 0; }