QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179502#5418. Color the Tree0x4F5DA2WA 1ms13876kbC++145.3kb2023-09-14 21:53:002023-09-14 21:53:01

Judging History

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

  • [2023-09-14 21:53:01]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：13876kb
查看
  • [2023-09-14 21:53:00]
  • 提交

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);
		/*if(T == 2998)
			printf("%d\n", n);*/
		for(int i = 0; i < n; ++i){
			scanf("%d", &st[0][i]);
			/*if(T == 2998)
				printf("%d ", st[0][i]);*/
		}
		/*if(T == 2998)
			putchar('\n');*/
		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))]);
			}
		}
		int u, v;
		for(int i = 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			
			if(T == 2998 && i > 16){
				printf("%d %d\n", u, v);
			}
			
			add_e(u, v);
			add_e(v, u);
		}
		if(T == 2998){
			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
75
36 8 15 37 10 42 19 33 10 41 45 47 39 20 13 7 21 17 16 8 27 23 41 34 26 9 16 33 25 18 18 42 20 24 28 12 27 16 45 33 12 30 31 37 17 8 39 7 18 13 12 12 32 47 50 12 31 49 26 27 22 39 42 12 46 34 37 31 5 33 28 19 25 12 12 
1 2
1 3
1 4
3 5
1 6
1 7
5 8
1 9
7 10
3 11
10 12
11 13
8 14
2 15
2 16
2 17
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11844kb

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: 1ms
memory: 13876kb

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
9 18
12 19
12 20
2 21
8 22
10 23
18 24
14 25
25 26
21 27
11 28
4 29
29 30
5 31
29 32
32 33
26 34
22 35
33 36
24 37
31 38
13 39
3 40
8 41
3 42
6 43
30 44
23 45
10 46
16 47
9 48
6 49
10 50
42 51
48 52
37 53
5 54
19 55
47 56
54 57
25 58
17 59
30 60
20 61
42 62
4 63
45 64
19 65
58 66
4 67
32 68
49 6...

result:

wrong answer 2nd numbers differ - expected: '168', found: '9'
English 繁體中文 简体中文

Server Time: 2024-12-05 07:52:11 | OpenSource Project