倍增法模板题
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define maxn 1000 #define DEG 20 struct Edge{ int to,next; }edge[maxn*maxn*2]; int head[maxn],tot; void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int fa[maxn][DEG]; int deg[maxn]; void bfs(int root){ queue<int> que; deg[root]=0; fa[root][0]=root; que.push(root); while(!que.empty()){ int tmp=que.front(); que.pop(); for(int i=1;i<DEG;i++) fa[tmp][i]=fa[fa[tmp][i-1]][i-1]; for(int i=head[tmp];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[tmp][0]) continue; deg[v]=deg[tmp]+1; fa[v][0]=tmp; que.push(v); } } } int lca(int u,int v){ if(deg[u]>deg[v]) swap(u,v); int hu=deg[u],hv=deg[v],tu=u,tv=v; for(int det=hv-hu,i=0;det;det>>=1,i++) if(det&1) tv=fa[tv][i];//将uv提到同一深度 if(tu==tv) return tu; for(int i=DEG-1;i>=0;i--){ if(fa[tu][i]==fa[tv][i]) continue; tu=fa[tu][i]; tv=fa[tv][i]; } return fa[tu][0]; } int ans[maxn],flag[maxn]; void init(){ tot=0; memset(ans,0,sizeof ans); memset(head,-1,sizeof head); memset(flag,0,sizeof flag); } int main(){ int n,u,v,m,q; while(scanf("%d",&n)==1){ init(); for(int i=1;i<=n;i++){ scanf("%d:(%d)",&u,&m); while(m--){ scanf("%d",&v); addedge(u,v); addedge(v,u); flag[v]=true; } } int root; for(int i=1;i<=n;i++) if(!flag[i]){root=i;break;} bfs(root); scanf("%d",&q); char c; while(q--){ cin>>c; scanf("%d %d)",&u,&v); ans[lca(u,v)]++; } for(int i=1;i<=n;i++) if(ans[i]) printf("%d:%d ",i,ans[i]); } return 0; }