oj.uz

Submission #784499

# Submission time Handle Problem Language Result Execution time Memory
784499 2023-07-16T07:30:59 Z blue Chase (CEOI17_chase) C++17
30 / 100
 438 ms 172928 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const int mxv = 100;

int n;
int m;

vll w(1+mx, 0);

vi edge[1+mx];

vi par(1 + mx, 0);

vll wsum(1+mx, 0);

void dfs(int u)
{
	for(int v : edge[u])
	{
		if(par[u] == v)
			continue;

		par[v] = u;
		dfs(v);
	}
}




ll up[1+mx][1+mxv];
ll dn[1+mx][1+mxv];

ll res = 0;

void dfs2(int u)
{
	for(int v : edge[u])
	{
		if(par[u] != v)
			dfs2(v);
	}




	//1. calculate up

	up[u][0] = 0;
	for(int k = 1; k <= m; k++)
		up[u][k] = wsum[u];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			up[u][k] = max(up[u][k], up[v][k]);
			if(k > 0)
				up[u][k] = max(up[u][k], up[v][k-1] + wsum[u] - w[v]);
		}
	}





	//2. calculate down

	dn[u][0] = 0;
	for(int k = 1; k <= m; k++)
		dn[u][k] = wsum[u] - w[par[u]];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			dn[u][k] = max(dn[u][k], dn[v][k]);

			if(k > 0)
				dn[u][k] = max(dn[u][k], dn[v][k-1] + wsum[u] - w[par[u]]);
		}
	}



	//3. update res

	//single element
	if(m >= 1)
		res = max(res, wsum[u]);

	//up path
	res = max(res, up[u][m]);

	//down path
	for(int v : edge[u])
	{
		if(par[u] != v)
		{
			res = max(res, dn[v][m]);
			if(m-1 >= 0)
				res = max(res, dn[v][m-1] + wsum[u]);
		}
	}

	//combination
	vll temp(1+m, -1'000'000'000'000'000'000LL);
	for(int v : edge[u])
	{
		if(par[u] == v)
			continue;

		for(int j = 0; j <= m; j++)
		{
			// res = max(res, temp0[m-j] + dn[v][j]);
			// res = max(res, temp1[m-j] + w[v] + dn[v][j]);
			res = max(res, temp[m-j] + dn[v][j]);
		}

		////////
		for(int j = 0; j <= m; j++)
		{
			temp[j] = max(temp[j], up[v][j]);
			if(j >= 1)
				temp[j] = max(temp[j], up[v][j] - w[v]);
		}
	}

	// for(int v1 : edge[u])
	// {
	// 	if(par[u] == v1)
	// 		continue;

	// 	for(int v2 : edge[u])
	// 	{
	// 		if(par[u] == v2)
	// 			continue;

	// 		if(v1 == v2)
	// 			continue;

	// 		for(int j = 0; j <= m; j++)
	// 		{
	// 			res = max(res, (up[v1][j]) + (dn[v2][m-j]));
	// 		}

	// 		for(int j = 0; j <= m-1; j++)
	// 		{
	// 			res = max(res, (wsum[u]) + (up[v1][j] - w[v1]) + (dn[v2][m-1-j]));
	// 		}
	// 	}
	// }
}





int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		cin >> w[i];

	for(int e = 1; e <= n-1; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	dfs(1);

	for(int i = 1; i <= n; i++)
		for(int j : edge[i])
			wsum[i] += w[j];

	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= m; j++)
		{
			up[i][j] = 0;
			dn[i][j] = 0;
		}
	}


	dfs2(1);


	// for(int i = 1; i <= n; i++)
	// {
	// 	for(int j = 0; j <= m; j++)
	// 		cerr << dn[i][j] << ' ';
	// 	cerr << '\n';
	// }

	cout << res << '\n';

}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Incorrect 2 ms 4564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Incorrect 2 ms 4564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 172928 KB Output is correct
2 Correct 258 ms 172892 KB Output is correct
3 Correct 438 ms 166280 KB Output is correct
4 Correct 117 ms 166896 KB Output is correct
5 Correct 265 ms 167024 KB Output is correct
6 Correct 259 ms 167016 KB Output is correct
7 Correct 275 ms 166916 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Incorrect 2 ms 4564 KB Output isn't correct
5 Halted 0 ms 0 KB -