problem

题目描述

如题&＃xff0c;给定一棵有根多叉树&＃xff0c;请求出指定两个点直接最近的公共祖先。

输入格式&＃xff1a;

第一行包含三个正整数N、M、S&＃xff0c;分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y&＃xff0c;表示x结点和y结点之间有一条直接连接的边&＃xff08;数据保证可以构成树&＃xff09;。

接下来M行每行包含两个正整数a、b&＃xff0c;表示询问a结点和b结点的最近公共祖先。

输出格式&＃xff1a;

输出包含M行&＃xff0c;每行包含一个正整数&＃xff0c;依次为每一个询问的结果。

输入样例#1&＃xff1a;

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例#1&＃xff1a;

4
4
1
4
4

思路

数据量可以到500000点 500000询问 提交果然卡常了

1.读入可以用getchar优化&＃xff08;次要&＃xff09;

2.vector较链表在数据量大的时候是慢的&＃xff08;希望有大神可以系统的说明下这个vector的复杂度分析&＃xff09;,可以用链式邻接表或者链式前向星模拟邻接表

代码示例(链式邻接表)

#include
using namespace std;
const int maxn&＃61;500010;//节点数struct Edge{int from,to;
}edges[2*maxn];const int maxlog&＃61;30;
int grand[maxn][maxlog];
//int gdis[maxn][maxlog];
//int gmax[maxn][maxlog];
int depth[maxn];
int n;//结点数
int s;//倍增最大步数
int root;//根节点
int cnt;//边集数struct EdgeNode{int adjvex;//顶点编号EdgeNode *next;
};struct AdList{int flag;EdgeNode *firstarc;
}G[maxn];void addEdge(int u,int v){//edges[cnt].from&＃61;v;//edges[cnt].to&＃61;head[u];//head[u]&＃61;cnt&＃43;&＃43;;edges[cnt].from&＃61;u;edges[cnt&＃43;&＃43;].to&＃61;v;//cout<<"添加"<EdgeNode *e;e&＃61;(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex&＃61;cnt-1;if(G[u].flag&＃61;&＃61;0) G[u].firstarc&＃61;NULL,G[u].flag&＃43;&＃43;;e->next&＃61;G[u].firstarc;G[u].firstarc&＃61;e;//cout<<"目前与节点"<//<adjvex<
}void init()
{cnt&＃61;0;memset(grand,0,sizeof(grand));//memset(head,-1,sizeof(head));memset(depth,0,sizeof(depth));//memset(gdis,0,sizeof(gdis));//memset(gmax,0,sizeof(gmax));
}void dfs(int x)//预处理
{for(int i&＃61;1;i<&＃61;s;&＃43;&＃43;i){grand[x][i]&＃61;grand[grand[x][i-1]][i-1];//gdis[x][i]&＃61;gdis[x][i-1]&＃43;gdis[grand[x][i-1]][i-1];//gmax[x][i]&＃61;max(gmax[x][i-1],gmax[grand[x][i-1]][i-1]);//if(!grand[x][i]) break;}for(int i&＃61;0;G[x].firstarc!&＃61;NULL;&＃43;&＃43;i){//cout<adjvex].to<<"TEST"<int tt&＃61;edges[G[x].firstarc->adjvex].to;G[x].firstarc&＃61;G[x].firstarc->next;if(tt!&＃61;grand[x][0]){depth[tt]&＃61;depth[x]&＃43;1;grand[tt][0]&＃61;x;//gdis[e.to][0]&＃61;e.dist;//gmax[e.to][0]&＃61;e.dist;dfs(tt);}}
}int lca(int a,int b)//最大值&＃xff0c;路径权值和
{if(depth[a]>depth[b]) swap(a,b);//ans&＃61;0;//路径权值和//maxx&＃61;gmax[b][0];//for(int i&＃61;s;i>&＃61;0;i--)// if(depth[a]&＃61;depth[a])// b&＃61;grand[b][i];int dre&＃61;depth[b]-depth[a];for(int i&＃61;s;i>&＃61;0;--i){if(dre&(1<if(a&＃61;&＃61;b) return a;for(int i&＃61;s;i>&＃61;0;i--)if(grand[a][i]!&＃61;grand[b][i]){//ans&＃43;&＃61;gdis[a][i],ans&＃43;&＃61;gdis[b][i];//maxx&＃61;max(maxx,gmax[a][i]),maxx&＃61;max(maxx,gmax[b][i]);a&＃61;grand[a][i],b&＃61;grand[b][i];}//ans&＃43;&＃61;gdis[a][0];//ans&＃43;&＃61;gdis[b][0];//maxx&＃61;max(maxx,gmax[a][0]);//maxx&＃61;max(maxx,gmax[b][0]);return grand[a][0];
}int read()
{char ch&＃61;&＃39;*&＃39;;while(!isdigit(ch&＃61;getchar()));//不是数字读掉int num&＃61;ch-&＃39;0&＃39;;while(isdigit(ch&＃61;getchar())) num&＃61;num*10&＃43;ch-&＃39;0&＃39;;return num;
}int main()
{init();int query,u,v,w;scanf("%d %d %d",&n,&query,&root);s&＃61;floor(log(n&＃43;0.0)/log(2.0))&＃43;1;for(int i&＃61;1;i<&＃61;n-1;&＃43;&＃43;i){u&＃61;read();v&＃61;read();addEdge(u,v);addEdge(v,u);}dfs(root);//以root为根结点建树for(int i&＃61;1;i<&＃61;query;&＃43;&＃43;i){u&＃61;read();v&＃61;read();printf("%d\n",lca(u,v));}return 0;
}

代码示例(链式向前星)

#include
using namespace std;
const int maxn&＃61;500010;//节点数struct Edge{int from,to;
}edges[2*maxn];const int maxlog&＃61;30;
int grand[maxn][maxlog];
//int gdis[maxn][maxlog];
//int gmax[maxn][maxlog];
int head[2*maxn];
int depth[maxn];
int n;//结点数
int s;//倍增最大步数
int root;//根节点
int cnt;//边集数void addEdge(int u,int v){edges[cnt].from&＃61;v;edges[cnt].to&＃61;head[u];head[u]&＃61;cnt&＃43;&＃43;;
}void init()
{cnt&＃61;0;memset(grand,0,sizeof(grand));memset(head,-1,sizeof(head));memset(depth,0,sizeof(depth));//memset(gdis,0,sizeof(gdis));//memset(gmax,0,sizeof(gmax));
}void dfs(int x)//预处理
{for(int i&＃61;1;i<&＃61;s;&＃43;&＃43;i){grand[x][i]&＃61;grand[grand[x][i-1]][i-1];//gdis[x][i]&＃61;gdis[x][i-1]&＃43;gdis[grand[x][i-1]][i-1];//gmax[x][i]&＃61;max(gmax[x][i-1],gmax[grand[x][i-1]][i-1]);//if(!grand[x][i]) break;}for(int i&＃61;head[x];i!&＃61;-1;i&＃61;edges[i].to){int tt&＃61;edges[i].from;if(tt!&＃61;grand[x][0]){depth[tt]&＃61;depth[x]&＃43;1;grand[tt][0]&＃61;x;//gdis[e.to][0]&＃61;e.dist;//gmax[e.to][0]&＃61;e.dist;dfs(tt);}}
}int lca(int a,int b)//最大值&＃xff0c;路径权值和
{if(depth[a]>depth[b]) swap(a,b);//ans&＃61;0;//路径权值和//maxx&＃61;gmax[a][0];//for(int i&＃61;s;i>&＃61;0;i--)// if(depth[a]&＃61;depth[a])// b&＃61;grand[b][i];int dre&＃61;depth[b]-depth[a];for(int i&＃61;s;i>&＃61;0;--i){if(dre&(1<if(a&＃61;&＃61;b) return a;for(int i&＃61;s;i>&＃61;0;i--)if(grand[a][i]!&＃61;grand[b][i]){//ans&＃43;&＃61;gdis[a][i],ans&＃43;&＃61;gdis[b][i];//maxx&＃61;max(maxx,gmax[a][i]),maxx&＃61;max(maxx,gmax[b][i]);a&＃61;grand[a][i],b&＃61;grand[b][i];}//ans&＃43;&＃61;gdis[a][0];//ans&＃43;&＃61;gdis[b][0];//maxx&＃61;max(maxx,gmax[a][0]);//maxx&＃61;max(maxx,gmax[b][0]);return grand[a][0];
}int read()
{char ch&＃61;&＃39;*&＃39;;while(!isdigit(ch&＃61;getchar()));//不是数字读掉int num&＃61;ch-&＃39;0&＃39;;while(isdigit(ch&＃61;getchar())) num&＃61;num*10&＃43;ch-&＃39;0&＃39;;return num;
}int main()
{init();int query,u,v,w;scanf("%d %d %d",&n,&query,&root);s&＃61;floor(log(n&＃43;0.0)/log(2.0))&＃43;1;for(int i&＃61;1;i<&＃61;n-1;&＃43;&＃43;i){u&＃61;read();v&＃61;read();addEdge(u,v);addEdge(v,u);}dfs(root);//以root为根结点建树for(int i&＃61;1;i<&＃61;query;&＃43;&＃43;i){u&＃61;read();v&＃61;read();printf("%d\n",lca(u,v));}return 0;
}