QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179490#5418. Color the Tree0x4F5DA2WA 28ms13828kbC++145.4kb2023-09-14 21:49:512023-09-14 21:49:51

Judging History

你现在查看的是最新测评结果

  • [2023-09-14 21:49:51]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:13828kb
  • [2023-09-14 21:49:51]
  • 提交

answer

#include <cstdio>
#include <algorithm>

const int maxn = 100000;
const long long LLF = 10000000000000000;
const int maxlog = 17;
struct node1{
	int nxt;
	int to;
}edge[maxn * 2 + 10];
int head[maxn + 10];
int top;
void add_e(int u, int v){
	++top;
	edge[top].nxt = head[u];
	edge[top].to = v;
	head[u] = top;
	return ;
}

int n;
int st[maxlog + 1][maxn + 10];
int log_2[maxn + 10];
int get_mina(int l, int r){
	int len = r - l + 1;
	int lg = log_2[len];
	return std::min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}

int dep[maxn + 10];
int max_dep;

int dfn[maxn + 10];
int top_dfn;

int fa[maxn + 10][maxlog + 1];

//存每个深度的点 
node1 edge2[maxn + 10];
int head2[maxn + 10];
int top2;
void add_e2(int u, int v){
	++top2;
	edge2[top2].nxt = head2[u];
	edge2[top2].to = v;
	head2[u] = top2;
}

//存虚树
node1 edge3[maxn + 10];
int head3[maxn + 10];
int top3;
void add_e3(int u, int v){
	//printf("%d->%d\n", u, v);
	++top3;
	/*if(head3[u] == top3){
		printf("cnm, %d, %d\n", u, v);
	}*/
	edge3[top3].nxt = head3[u];
	edge3[top3].to = v;
	head3[u] = top3;
}

void dfs1(int x){
	dep[x] = dep[fa[x][0]] + 1;
	if(max_dep < dep[x])
		max_dep = dep[x];
	add_e2(dep[x], x);
	/*if(dep[x] == 5)
		printf("%d->%d\n", dep[x], x);*/
	dfn[x] = ++top_dfn;
	for(int i = head[x]; i; i = edge[i].nxt){
		int y = edge[i].to;
		if(y != fa[x][0]){
			fa[y][0] = x;
			dfs1(y);
		}
	}
}

int LCA(int x, int y){
	if(dep[x] < dep[y]){
		int temp = x;
		x = y;
		y = temp;
	}
	for(int i = maxlog; i >= 0; --i){
		if(dep[x] - (1 << i) >= dep[y]){
			x = fa[x][i];
		}
	}
	if(x == y)
		return x;
	for(int i = maxlog; i >= 0; --i){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

int key_node[maxn + 10];
int top_key;
bool cmp(int a, int b){
	return dfn[a] < dfn[b];
}
int sta[maxn + 10];
int tops;

long long ans[maxn + 10];
long long dp[maxn + 10];
int now_d;
void dfs2(int x, int fa){
	if(dep[x] == now_d){
		dp[x] = (long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]);
		return ;
	}
	long long temp = 0;
	for(int i = head3[x]; i; i = edge3[i].nxt){
		int y = edge3[i].to;
		//printf("%d:%d\n", i, edge3[i].nxt);
		//printf("%d->%d\n", x, y);
		dfs2(y, x);
		temp = temp + dp[y];
	}
	dp[x] = std::min((long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]), temp);
	return ;
}

int main(){
	log_2[1] = 0;
	for(int i = 2; i <= maxn; ++i){
		log_2[i] = log_2[(i >> 1)] + 1;
	}
	
	int T;
	scanf("%d", &T);
//	if(T == 3000)
//		T = 1;
	while(T--){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", &st[0][i]);
		}
		for(int i = 1; i <= maxlog; ++i){
			for(int j = 0; j + (1 << i) - 1 < n; ++j){
				st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
		/*if(T == 3000){
			return 0;
		}*/
		int u, v;
		for(int i = 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			
			/*if(T == 2999 && i > 26){
				printf("#%d %d\n", u, v);
			}*/
			
			add_e(u, v);
			add_e(v, u);
		}
		/*if(T == 2999){
			return 0;
		}*/
		fa[1][0] = 0;
		dfs1(1);
		for(int i = 1; i <= maxlog; ++i){
			for(int j = 1; j <= n; ++j){
				fa[j][i] = fa[fa[j][i - 1]][i - 1];
			}
		}
		
		/*while(1){
			scanf("%d%d", &u, &v);
			printf("%d\n", LCA(u, v));
		}*/
		
		long long final_ans = 0;
		
		for(int i = 1; i <= max_dep; ++i){
			//建立虚树 
			top_key = 0;
			tops = 0;
			for(int j = head2[i]; j; j = edge2[j].nxt){
				++top_key;
				key_node[top_key] = edge2[j].to;
			}
			std::sort(key_node + 1, key_node + 1 + top_key, cmp);
			++tops;
			sta[tops] = 1;
			head3[1] = 0;
			for(int j = 1; j <= top_key; ++j){
				if(key_node[j] == 1)
					continue ;
				int l = LCA(key_node[j], sta[tops]);
				if(l != sta[tops]){
					while(dfn[l] < dfn[sta[tops - 1]]){
						add_e3(sta[tops - 1], sta[tops]);
						--tops;
					}
					if(dfn[l] > dfn[sta[tops - 1]]){
						head3[l] = 0;
						add_e3(l, sta[tops]);
						sta[tops] = l;
					}
					else{
						add_e3(l, sta[tops]);
						--tops;
					}
				}
				head3[key_node[j]] = 0;
				++tops;
				sta[tops] = key_node[j];
			}
			for(int j = 1; j < tops; ++j){
				add_e3(sta[j], sta[j + 1]);
			}
			
			//debug
			/*printf("%d:\n", i);
			for(int j = 1; j <= top_key; ++j){
				printf("%d ", key_node[j]);
			}
			putchar('\n');
			for(int j = 1; j <= tops; ++j){
				printf("%d ", sta[j]);
			}
			putchar('\n');*/
			
			//计算 
			now_d = i;
			dfs2(1, 0);
			
			final_ans = final_ans + dp[1];
			
			//清空 
			top3 = 0;
			/*head3[1] = 0;
			for(int j = 1; j <= top_key; ++j){
				head3[key_node[j]] = 0;
			}*/
		}
		
		printf("%lld\n", final_ans);
		
		
		//清空
		top2 = 0;
		for(int i = 1; i <= max_dep; ++i)
			head2[i] = 0;
			
		top = 0;
		for(int i = 1; i <= n; ++i){
			head[i] = 0;
		}
		max_dep = 0;
		top_dfn = 0;
	}
	return 0;
} 
/*
1
54
43 44 11 49 17 
14 7 30 35 12 
34 14 15 8 29 
47 30 31 39 17 
26 23 26 45 34 
50 49 13 35 18 
29 15 13 44 47 
5 22 20 19 46 
30 22 26 13 47 
46 43 27 48 48 
13 14 30 44
1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28
13 29
10 30
18 31
4 32
9 33
27 34
20 35
32 36
9 37
31 38
38 39
13 40
3 41
41 42
5 43
38 44
12 45
2 46
37 47
12 48
18 49
48 50
33 51
28 52
25 53
16 54
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9816kb

input:

3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4

output:

35
17
1218

result:

ok 3 number(s): "35 17 1218"

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 13828kb

input:

3000
54
43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44
1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28...

output:

180
180
224
237
161
273
225
145
105
87
165
87
168
154
193
142
251
230
153
233
153
171
80
282
234
286
204
211
119
203
211
234
88
252
239
240
199
184
217
129
109
164
195
201
226
210
182
139
243
59
56
31
127
209
203
172
173
225
53
144
189
174
175
141
233
107
181
273
80
394
161
133
157
159
240
281
146
2...

result:

wrong answer 2nd numbers differ - expected: '168', found: '180'