Submission #113903

#	Time	Username	Problem	Language	Result	Execution time	Memory
113903		Mahdi_Jfri	Chase (CEOI17_chase)	C++14	100 / 100	856 ms	390496 KiB

chase

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;
const int maxv = 1e2 + 20;

int x[maxn];

vector<int> adj[maxn];

ll dpd[maxn][maxv][2] , mx[maxv][2] , dpu[maxn][maxv][2] , sum[maxn];

void dfs(int v , int p = -1)
{
	dpd[v][0][1] = -1e18;
	for(int i = 1; i < maxv; i++)
		dpd[v][i][1] = sum[v];

	for(auto u : adj[v])
		if(u != p)
		{
			dfs(u , v);

			for(int i = 0; i < maxv; i++)
			{
				if(i)
				{
					dpd[v][i][1] = max(dpd[v][i][1] , dpd[u][i - 1][0] + sum[v]);
					dpd[v][i][1] = max(dpd[v][i][1] , dpd[u][i - 1][1] + sum[v] - x[v]);
				}

				dpd[v][i][0] = max(dpd[v][i][0] , dpd[u][i][0]);
				dpd[v][i][0] = max(dpd[v][i][0] , dpd[u][i][1] - x[v]);
			}
		}
}

void sfd(int v , int p = -1)
{
	dpu[v][0][1] = -1e18;
	for(int i = 1; i < maxv; i++)
		dpu[v][i][1] = max(dpu[v][i][1] , sum[v]);

	for(int _ = 0; _ < 2; _++)
	{
		reverse(adj[v].begin() , adj[v].end());
		for(int i = 0; i < maxv; i++)
			mx[i][0] = dpu[v][i][0] , mx[i][1] = dpu[v][i][1];

		for(auto u : adj[v])
			if(u != p)
			{
				for(int i = 0; i < maxv; i++)
				{
					if(i)
					{
						dpu[u][i][1] = max(dpu[u][i][1] , mx[i - 1][0] + sum[u]);
						dpu[u][i][1] = max(dpu[u][i][1] , mx[i - 1][1] + sum[u] - x[u]);
					}

					dpu[u][i][0] = max(dpu[u][i][0] , mx[i][0]);
					dpu[u][i][0] = max(dpu[u][i][0] , mx[i][1] - x[u]);
				}

				for(int i = 0; i < maxv; i++)
				{
					if(i)
					{
						mx[i][1] = max(mx[i][1] , dpd[u][i - 1][0] + sum[v]);
						mx[i][1] = max(mx[i][1] , dpd[u][i - 1][1] + sum[v] - x[v]);
					}

					mx[i][0] = max(mx[i][0] , dpd[u][i][0]);
					mx[i][0] = max(mx[i][0] , dpd[u][i][1] - x[v]);
				}
			}
	}

	for(auto u : adj[v])
		if(u != p)
			sfd(u , v);
}

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

	int n , v;
	cin >> n >> v;

	for(int i = 0; i < n; i++)
		cin >> x[i];

	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);

		sum[a] += x[b] , sum[b] += x[a];
	}

	dfs(0);
	sfd(0);

	ll res = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 2; j++)
			res = max(res , max(dpd[i][v][j] , dpu[i][v][j]));

	cout << res << endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30