hdu 4679 Terrorist’s destroy

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

树dp

做法是枚举每一条边，删除它，然后得到删除这条边的答案，再更新最后的答案

所以枚举答案的复杂度是O(n)

要做两次dfs，每个dfs其实就是遍历一次整个树，所以两次dfs的复杂度也是O(n)

所以整个算法的复杂度是O(n)，但是常数应该是很大的，因为每到达一个点

更新很多信息

两次dfs都是以1为根，向下dfs的

  1. dfs1是递归回溯的时候更新信息，所以是一个 自底向上 的更新
  2. dfs2是递归下去的时候传递信息，所以是一个 自顶向下 的更新

主要记录的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int leaf[N][3],idl[N][3];
//leaf[u][]表示点u，走到叶子的最大，次大，次次大距离
//idl[u][]，是对应leaf数组的一个标记，标记u是从它的哪个儿子走下去的
int Max[N];
//Max[u]，以u为根的子树（包括点u），所能找到的最长链
int SonMax[N][2],idS[N][2];
//SonMax[u][]，以u为根的子树中，u的两个儿子v0，v1，它们的最长链，而且这两个最长链所有最长链的最大值和次大值
//即 SonMax[u][0] = Max[v0]; SonMax[u][1] = Max[v1];
//idS[u]是一个标记，idS[u][0] = v0; idS[u][1] = v1;
int back[N];
//back[u]，从u开始往上祖先方向走出的一条最长链
int MaxUp[N];
//点u的上方（不包括点u，不包括点u的所有子孙后代，而是从点u父亲算起），能找到的最长链
int ans,index;

怎么更新答案？
找到一条边u->v，在树中u是v的父亲

树断裂为两个部分，先算点v为子树的那部分的最长链

显然是Max[v]

之后是算点u，以及点u余下的其他儿子分支，以及u的上方，这3部分的最长链

这3部分用文字很难描述，主要看dfs2里面的所有更新

代码中奖所有更新都用函数来写

void updata_xxxxx() 这样的函数都是更新函数，xxxx就是对应要更新的数组

//最后，我觉得正解可能比我想的简单，我觉得我想复杂了，但是现在还没有想出简单的更新

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n;
struct edge{
	int v,w,id;
	edge(){}
	edge(int __v,int __w,int __id){
		v = __v; w = __w; id = __id;
	}
};
vector<edge>e[N];
int leaf[N][3],idl[N][3];
int Max[N];
int SonMax[N][2],idS[N][2];
int back[N];
int MaxUp[N];
int ans,index;

void updata_leaf(int u,int v){
	if(leaf[v][0] + 1 > leaf[u][0]){
		for(int i = 2; i > 0; i--){
			leaf[u][i] = leaf[u][i-1]; idl[u][i] = idl[u][i-1];
		}
		leaf[u][0] = leaf[v][0] + 1; idl[u][0] = v;
	}
	else if(leaf[v][0] + 1 > leaf[u][1]){
		leaf[u][2] = leaf[u][1]; idl[u][2] = idl[u][1];
		leaf[u][1] = leaf[v][0] + 1; idl[u][1] = v;
	}
	else if(leaf[v][0] + 1 > leaf[u][2]){
		leaf[u][2] = leaf[v][0] + 1; idl[u][2] = v;
	}
}

void updata_SonMax(int u,int v){
	if(Max[v] > SonMax[u][0]){
		SonMax[u][1] = SonMax[u][0]; idS[u][1] = idS[u][0];
		SonMax[u][0] = Max[v]; idS[u][0] = v;
	}
	else if(Max[v] > SonMax[u][1]){
		SonMax[u][1] = Max[v]; idS[u][1] = v;
	}
}

void updata_Max(int u){
	Max[u] = max(SonMax[u][0] , leaf[u][0] + leaf[u][1]);
}

void dfs1(int u,int fa){
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].v;
		if(v == fa) continue;
		dfs1(v,u);
		updata_leaf(u,v);
		updata_SonMax(u,v);
	}
	updata_Max(u);
}

void updata_back(int u,int fa){
	if(idl[fa][0] != u){
		back[u] = leaf[fa][0];
	}
	else if(idl[fa][1] != -1){
		back[u] = leaf[fa][1];
	}
	if(back[fa] > back[u]) 
		back[u] = back[fa];
	++back[u];
}

int updata_sum_leaf(int u,int fa){
	int res = 0,tmp;
	if(idl[fa][0] == u){
		tmp = leaf[fa][1] + max(leaf[fa][2],back[fa]);
		res = max(res,tmp);
	}
	else if(idl[fa][1] == u){
		tmp = leaf[fa][0] + max(leaf[fa][2],back[fa]);
		res = max(res,tmp);
	}
	else if(idl[fa][2] == u){
		tmp = leaf[fa][0] + max(leaf[fa][1],back[fa]);
		res = max(res,tmp);
	}
	else{
		tmp = leaf[fa][0] + max(leaf[fa][1],back[fa]);
		res = max(res,tmp);
	}
	return res;
}

void updata_MaxUp(int u,int fa){
	MaxUp[u] = MaxUp[fa];
	if(idS[fa][0] != u)
		MaxUp[u] = max(MaxUp[u],SonMax[fa][0]);
	else if(idS[fa][1] != u)
		MaxUp[u] = max(MaxUp[u],SonMax[fa][1]);
	
	int sum_leaf = updata_sum_leaf(u,fa);
	MaxUp[u] = max(MaxUp[u],sum_leaf);
}

void updata_ans(int u,int v,int w,int id){
	int res[5]; 
	cl(res,0);
	res[1] = Max[v];
	if(idS[u][0] != v)
		res[2] = max(res[2],SonMax[u][0]);
	else if(idS[u][1] != v)
		res[2] = max(res[2],SonMax[u][1]);
	res[3] = updata_sum_leaf(v,u);
	res[4]= MaxUp[u];
	for(int i = 1; i <= 4; i++)
		res[0] = max(res[0],res[i]);
	if(res[0] * w < ans){
		ans = res[0] * w; index = id;
	}
	else if(res[0] * w == ans && id < index){
		ans = res[0] * w; index = id;
	}
}

void dfs2(int u,int fa){
	if(fa != -1){
		updata_back(u,fa);
		updata_MaxUp(u,fa);
	}
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].v;
		int w = e[u][i].w;
		int id = e[u][i].id;
		if(v == fa) continue;
		dfs2(v,u);
		updata_ans(u,v,w,id);
	}
}

int main(){
	int T;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas++){
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
			e[i].clear();
		for(int i = 1; i < n; i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			e[u].pb(edge(v,w,i));
			e[v].pb(edge(u,w,i));
		}
		cl(leaf,0); cl(idl,-1);
		cl(Max,0);
		cl(SonMax,0); cl(idS,-1);
		cl(back,0);
		cl(MaxUp,0);

		dfs1(1,-1);
		ans = INF; index = -1;
		dfs2(1,-1);
		printf("Case #%d: %d\n",cas,index);
		//Test();
	}
	return 0;
}

//打印两次DFS记录下的信息
/*
void Test(){
	puts("leaf");
	for(int i = 1; i <= n; i++)
		printf("%d : %d[%d]  %d[%d]  %d[%d]\n",i,leaf[i][0],idl[i][0],
		leaf[i][1],idl[i][1],leaf[i][2],idl[i][2]);
	puts("back");
	for(int i = 1; i <= n; i++)
		printf("%d : %d\n",i,back[i]);
	puts("SonMax");
	for(int i = 1; i <= n; i++)
		printf("%d : %d[%d]\n",i,SonMax[i][0],idS[i][0],
		SonMax[i][1],idS[i][1]);
	puts("Max");
	for(int i = 1; i <= n; i++)
		printf("%d : %d\n",i,Max[i]);
	puts("MaxUp");
	for(int i = 1; i <= n; i++)
		printf("%d : %d\n",i,MaxUp[i]);
}
*/