<题目链接>
题目大意:
给你一棵树,然后进行q次询问,然后要你统计这q次询问中指定的两个节点最近公共祖先出现的次数。
解题分析:
LCA模板题,下面用的是离线Tarjan来解决。并且为了代码的简洁,本代码用的是vector存图。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; ; vector<int>edge[N]; int query[N][N],father[N],count[N],indeg[N]; bool vis[N]; int n,m; void init(){ ;i<=n;i++)edge[i].clear(); memset(query,,sizeof(query)); memset(vis,false,sizeof(vis)); memset(count,,sizeof(count)); memset(indeg,,sizeof(indeg)); } int find(int x){ //找到根节点 if(x!=father[x]) father[x]=find(father[x]); return father[x]; } void Tarjan(int u){ father[u]=u; ;i<edge[u].size();i++){ //得到该树上所有节点的父子关系 int v=edge[u][i]; Tarjan(v); father[v]=u; } vis[u]=true; ;i<=n;i++) if(vis[i] && query[u][i]) count[find(i)]+=query[u][i]; //最近公共祖先出现次数+1 } int main(){ while(~scanf("%d",&n)){ init(); int u,v; ;i<n;i++){ scanf("%d:(%d)",&u,&m); while(m--){ scanf(" %d",&v); edge[u].push_back(v); //建立有向边 indeg[v]++; //统计入度,用于寻找根节点 } } scanf(" %d",&m); ;i<m;i++){ scanf(" (%d %d)",&u,&v); query[u][v]++; //将代查询的节点也全部记录下来 query[v][u]++; } ;i<=n;i++) ){ Tarjan(i); break; } ;i<=n;i++) if(count[i]) printf("%d:%d\n",i,count[i]); } ; }
2018-10-21