G-rated

What are you waiting for?

0%

hdu 4008 Parent and son

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意：给定一个无根树，接着是一系列的询问。每个询问给出x，y，以x为根，找出y为根的子树中的最小儿子和最小子孙（子孙包括儿子）

步骤：

  1. 无根树问题要确定一个根，定根要根据实际问题来定，这题以1为根，然后遍历整个树，并记录信息。
  2. 先分类讨论整个问题，再讲需要记录什么信息。下面的分类讨论都是以1为整个树的树根为基础来讨论的
    1. 当x是y的祖先：那么只需要考虑y的子树，直接找出最小儿子和最小子孙
    2. 当x和y无直属关系（兄弟或者更远的关系）：那么同样是只需要考虑y的子树，直接输出最小儿子和最小子孙
    3. 当x是y的子孙后代（包括可能是y的儿子）：这个情况也需要分y是1或不是1来讨论
      1. 当y不是1：
        • 怎么找最小儿子？从x回到y的路径上，找到离y最近的那个儿子z，也就是z是x所在的那个分支的祖先。如果z不是y的最小儿子，那么答案就是min(最小儿子,fa[y]),不要漏掉fa[y]；如果z就是y的最小儿子，那么答案就是min(次小儿子，fa[y])，同样不要漏掉fa[y]。
        • 怎么找最小子孙呢？这个简单，直接就是1
      2. 当y是1：
        • 怎么找最小儿子？从x回到y的路径上，找到离y最近的那个儿子z，也就是z是x所在的那个分支的祖先。如果z不是y的最小儿子，那么答案就是最小儿子；如果z是最小儿子，那么答案就是次小儿子。
        • 怎么找最小子孙？要从整个分支来考虑，以1为根，把下面的子树看做一个一个的大分支，例如1有3个儿子那么就有3个分支，每个分支有1个代表，就是树最顶部的那个树根。找出1的最小子孙所在的分支ance1，次小子孙所在的分支ance2，x所在的分支ance3。如果ance1 != ance3 ，那么就可以选最小子孙因为不在一个分支内；否则看ance2，ance2 != ance3，那么可以选次小子孙。如果三者都在一个分支内，那么就在其他分支内找一个最小子孙即可。
  3. 记录的信息
  • 每个节点的最小儿子，次小儿子
  • 每个节点的最小子孙，次小子孙
  • 每个节点的父亲。
  • 以1为根，每个节点属于哪个分支
  • 以1为根，每个分支的兄弟分支的最小分支
  • 要确定两个节点是不是祖先后裔关系，要记录前序遍历过程过访问每个节点的首次时间和末次时间，可以快速判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream&gt;
#include <cstdio&gt;
#include <cstring&gt;
#include <vector&gt;
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define cl memset

int n,tot,head[N];
struct edge{
	int v,next;
}e[2*N];
int first[N],last[N],dcnt;       //每个节点的首次和末次访问时间
int fa[N],depth[N];              //以1为树根每个节点的父亲，深度
int childen[N][2],des[N][2];     //每个节点的最小次小儿子，最小次小后裔
int bro[N];                      //以1为根的所有分支中，除自身外所有其他分支的最小值
int min1,min2,index1,index2;     //以1为根的分支中的最小次小值，以及它们属于哪个分支
int ance[N];                     //每个节点回到1的路径上，离1最近的那个祖先

inline void add(int u,int v){
	e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}

inline void updata(int u,int v){
	//更新儿子
	if(v < childen[u][0]){
		childen[u][1] = childen[u][0];
		childen[u][0] = v;
	}
	else if(v < childen[u][1])
		childen[u][1] = v;
	//更新子孙后代
	int Min1,Min2;
	Min1 = min(v,des[v][0]);
	Min2 = (Min1 == v) ? des[v][0] : min(v,des[v][1]);
	if(Min1 < des[u][0]){
		des[u][1] = des[u][0];
		des[u][0] = Min1;
	}
	else if(Min1 < des[u][1])
		des[u][1] = Min1;
	if(Min2 < des[u][1])
		des[u][1] = Min2;

}
void dfs(int u,int par,int dep,int __ance){
	first[u] = ++dcnt; 
	fa[u] = par; depth[u] = dep;
	if(dep == 2)	 ance[u] = u;
	else if(dep &gt; 2) ance[u] = __ance;
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		if(v == par) continue;
		int temp = (dep == 2) ? u : __ance;
		dfs(v,u,dep+1,temp);
		updata(u,v);
		if(u == 1){
			int Min = min(v,min(des[v][0],des[v][1]));
			if(Min <  min1){
				min2 = min1; index2 = index1;
				min1 = Min;  index1 = v;
			}
			else if(Min < min2){
				min2 = Min; index2 = v;
			}
		}
	}
	last[u] = ++dcnt;
}

inline bool check(int u ,int v){ //u是v的祖先或者无直属关系，true；u是v的后裔，false
	if(first[v] < first[u] && last[u] < last[v])
		return false;
	return true;
}

int main(){
	int cas,q;
	scanf("%d",&cas);
	while(cas--){
//	while(scanf("%d%d",&n,&q)!=EOF){
		scanf("%d%d",&n,&q);
		tot = dcnt = 0;
		min1 = min2 = INF;
		index1 = index2 = -1;
		cl(childen,0x3f,sizeof(childen));
		cl(des,0x3f,sizeof(des));
		cl(bro,0x3f,sizeof(bro));
		cl(head,-1,sizeof(head));
		for(int i = 1; i < n; i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
		}

		dfs(1,INF,1,-1);
		for(int k = head[1]; k != -1; k = e[k].next){
			int v = e[k].v;
			if(v != index1) bro[v] = min1;
			else			bro[v] = min2;
		}
//		TEST();
		while(q--){
			int u,v,res,__res;
			scanf("%d%d",&u,&v);
			if(check(u,v)){ //最简单的情况
				res = childen[v][0]; 
				__res = des[v][0];
				if(res == INF) puts("no answers!");
				else		   printf("%d %d\n",res,__res);
			} 
			else{
				if(childen[v][0] == u || !check(u,childen[v][0])) 
					res = min(childen[v][1],fa[v]);
				else 
					res = min(childen[v][0],fa[v]);
				if(res == INF){
					puts("no answers!");
					continue;
				}
				if(v != 1)
					__res = 1;
				else{
					int ance1 = ance[des[1][0]];
					int ance2 = ance[des[1][1]];
					int ance3 = ance[u];
					if(ance1 != ance3)      __res = des[1][0];
					else if(ance2 != ance3) __res = des[1][1];
					else					__res = bro[ance3];
				}
				printf("%d %d\n",res,__res);
			}
		}
		puts("");
	}
	return 0;
}

/*
void TEST(){
	puts("first    last");
	for(int i = 1; i <= n; i++)
		printf("%d: %d  %d\n",i,first[i],last[i]);
	puts("fa   ance");
	for(int i = 2; i <= n; i++)
		printf("%d: %d  %d\n",i,fa[i],ance[i]);
	puts("childen");
	for(int i = 1; i <= n; i++)
		printf("%d: %d  %d\n",i,childen[i][0],childen[i][1]);
	puts("des");
	for(int i = 1; i <= n; i++)
		printf("%d: %d  %d\n",i,des[i][0],des[i][1]);
	printf("min1 = %d | index1 = %d | min2 = %d | index2 = %d\n",min1,index1,min2,index2);
	puts("bro");
	for(int i = 1; i <= n; i++)
		printf("%d: %d\n",i,bro[i]);
}
*/