QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#180962	#6438. Crystalfly	0x4F5DA2	WA	92ms	1656kb	C++14	1.4kb	2023-09-16 14:45:44	2023-09-16 14:45:45

Judging History

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

[2023-09-16 14:45:45]
评测

测评结果：WA
用时：92ms
内存：1656kb

查看

[2023-09-16 14:45:44]
提交

answer

#include <cstdio>
const int maxn = 100000;
int n;
int a[maxn + 10];
int t[maxn + 10];

struct node{
	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 ;
}

long long dp[maxn + 10][2];
void dfs(int x, int fa){
	dp[x][0] = dp[x][1] = 0;
	int ap1 = 0, ap2 = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
		int y = edge[i].to;
		if(y != fa){
			dfs(y, x);
			if(a[ap1] < a[y]){
				ap1 = y;
			}
			if(t[y] == 3 && a[ap2] < a[y]){
				ap2 = y;
			}
			dp[x][1] = dp[x][1] + dp[y][0];
		}
	}
	//第一种，不管t=3 
	dp[x][0] = dp[x][1] + a[ap1];
	//第二种，考虑t=3 
	for(int i = head[x]; i; i = edge[i].nxt){
		int y = edge[i].to;
		if(y != fa && y != ap2){
			long long temp = dp[x][1] + a[ap2] - dp[y][0] + dp[y][1] + a[y];
			if(dp[x][0] < temp){
				dp[x][0] = temp;
			}
		}
	}
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			scanf("%d", &a[i]);
		}
		for(int i = 1; i <= n; ++i){
			scanf("%d", &t[i]);
		}
		int u, v;
		for(int i = 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			add_e(u, v);
			add_e(v, u);
		}
		dfs(1, 0);
		
		printf("%lld\n", dp[1][0] + a[1]);
		
		top = 0;
		for(int i = 1; i <= n; ++i){
			head[i] = 0;
		}
	}
	return 0;
} 

/*
1
6
6 4 4 1 3 6
2 1 3 3 3 3
1 2
1 3
3 4
4 5
5 6
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 1628kb

input:

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

output:

10101
10111

result:

ok 2 number(s): "10101 10111"

Test #2:

score: 0

Accepted

time: 0ms

memory: 1560kb

input:

10
6
8 1 1 5 8 9
2 1 2 2 2 2
1 2
2 3
2 4
1 5
2 6
6
6 4 4 1 3 6
2 1 3 3 3 3
1 2
1 3
3 4
4 5
5 6
6
10 5 1 8 5 1
1 3 1 2 2 2
1 2
2 3
2 4
2 5
3 6
10
6 8 8 9 6 9 5 6 6 4
2 1 3 3 2 2 2 2 3 1
1 2
1 3
3 4
4 5
5 6
4 7
2 8
7 9
9 10
7
10 9 1 5 7 5 4
1 1 1 2 1 3 2
1 2
1 3
3 4
3 5
5 6
1 7
5
7 1 1 4 2
3 1 3 2 2
1...

output:

result:

ok 10 numbers

Test #3:

score: -100

Wrong Answer

time: 92ms

memory: 1656kb

input:

100000
10
9 1 7 9 5 1 10 5 3 8
2 1 1 3 1 2 2 3 3 1
1 2
2 3
3 4
1 5
2 6
2 7
6 8
7 9
7 10
3
6 6 1
2 1 2
1 2
1 3
10
6 5 3 7 1 5 1 9 7 3
3 1 3 3 1 3 2 2 2 3
1 2
1 3
3 4
4 5
2 6
6 7
4 8
7 9
1 10
7
2 8 9 7 7 9 10
2 3 2 2 3 2 1
1 2
2 3
1 4
3 5
4 6
3 7
1
8
1
1
4
2
7
9 9 9 8 4 2 7
3 1 2 1 1 1 1
1 2
2 3
2 4
3...

output:

result:

wrong answer 3rd numbers differ - expected: '41', found: '40'