首页 > 代码库 > HDU 4008 Parent and son LCA+树形dp
HDU 4008 Parent and son LCA+树形dp
题意:
给定case数
给定n个点的树,m个询问
下面n-1行给出树边
m个询问 x y
问:以x为根,y子树下 y的最小点标的儿子节点 和子孙节点
思路:
用son[u][0] 表示u的最小儿子 son[u][2] 表示u的次小儿子
son[u][1] 表示u的最小子孙
若lca(x,y) !=y 则就是上述的答案
若lca(x,y) == y
1、y != 1 那么最小儿子就是除了x外的节点,且此时father[y] 也是y的儿子节点, 而最小的子孙节点就是1
2、y==1 那么特殊处理一下,用map维护一下除了u节点下的子树,1的最小子孙节点
#include <stdio.h> #include <iostream> #include <algorithm> #include <sstream> #include <stdlib.h> #include <string.h> #include <limits.h> #include <string> #include <time.h> #include <math.h> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define inf 1000000 #define N 100050 struct Edge{ int from, to, dis, nex; }edge[5*N]; int head[N],edgenum,dis[N],fa[N][20],dep[N]; //fa[i][x] 是i的第2^x个父亲(如果超过范围就是根) void add(int u,int v,int w){ Edge E={u,v,w,head[u]}; edge[edgenum] = E; head[u]=edgenum++; } void bfs(int root){ queue<int> q; fa[root][0]=root;dep[root]=0;dis[root]=0; q.push(root); while(!q.empty()){ int u=q.front();q.pop(); for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u]; ~i;i=edge[i].nex){ int v=edge[i].to;if(v==fa[u][0])continue; dep[v]=dep[u]+1;dis[v]=dis[u]+edge[i].dis;fa[v][0]=u; q.push(v); } } } int move(int x,int y){//把x移动到y下面 int D = dep[x] - dep[y]-1; while(D){ int z = (int)(log10(1.0*D)/log10(2.0)); x = fa[x][z]; D-=1<<z; } return x; } int Lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void init(){memset(head, -1, sizeof head); edgenum = 0;} int son[N][3], Fa[N]; //0是最小 1是子孙最小 2是次小 void dfs(int u,int father){ Fa[u] = father; son[u][0] = son[u][1] = son[u][2] = inf; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(v==father)continue; dfs(v,u); if(v<son[u][0]) son[u][2] = son[u][0], son[u][0] = v; else son[u][2] = min(son[u][2], v); son[u][1] = min(son[u][1], son[v][1]); } son[u][1] = min(son[u][1], son[u][0]); } map<int,int>mp; bool work(int x,int y){ int lca = Lca(x,y), son1, son2; if(lca==y) { x = move(x,y); son1 = son[y][0]; if(son1 == x) son1 = son[y][2]; son1 = min(son1, Fa[y]); if(y==1) { son2 = mp[x]; } else son2 = 1; } else { son1 = son[y][0]; son2 = son[y][1]; } if(son1==inf||son2==inf)return false; printf("%d %d\n",son1,son2); return true; } int n; int main(){ int i,j,u,v,T,que;scanf("%d",&T); while(T--){ init(); scanf("%d %d",&n,&que); for(i = 1; i < n; i++) { scanf("%d %d",&u,&v); add(u,v,1); add(v,u,1); } bfs(1); dfs(1,1); Fa[1] = inf; mp.clear(); int fir = inf, sec = inf; for(i = head[1]; ~i; i = edge[i].nex){ v = edge[i].to; mp[v] = inf; if(v<fir)sec = fir, fir = v; else sec = min(sec, v); } for(i = head[1]; ~i; i = edge[i].nex){ v = edge[i].to; if(v!=fir)mp[v] = fir; else mp[v] = sec; } fir = inf; sec = inf; for(i = head[1]; ~i; i = edge[i].nex){ v = edge[i].to; if(son[v][1]<fir)sec = fir, fir = son[v][1]; else sec = min(sec, son[v][1]); } for(i = head[1]; ~i; i = edge[i].nex){ v = edge[i].to; if(son[v][1]!=fir) mp[v] = min(mp[v], fir); else mp[v] = min(mp[v], sec); } while(que--){ scanf("%d %d",&u,&v); if(work(u,v)==false) puts("no answers!"); } puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。