Submission #1283124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283124		thuhienne	Travelling Trader (CCO23_day2problem2)	C++20	11 / 25	106 ms	44876 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define re exit(0);

int n,k;
vector <int> adj[200009];
int gain[200009];

long long dp[200009],res;
vector <int> sol;

void dfs1(int node,int par) {
	dp[node] = gain[node];
	for (auto x : adj[node]) if (x != par) {
		dfs1(x,node);
		dp[node] = max(dp[node],dp[x] + gain[node]);
	}
	res = max(res,dp[node]);
}
void trace1(int node,int par) {
	sol.push_back(node);
	int maxchild = 0;
	for (auto x : adj[node]) if (x != par) {
		if (maxchild == 0 || dp[maxchild] < dp[x]) maxchild = x;
	}
	if (maxchild == 0) return;
	trace1(maxchild,node);
}

void dfs3(int node,int par) {
	sol.push_back(node);
	for (auto x : adj[node]) if (x != par) {
		for (auto y : adj[x]) if (y != node) {
			dfs3(y,x);
		}
		sol.push_back(x);
	}
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);

	cin >> n >> k;
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) cin >> gain[i];
	
	if (k == 1) {
		dfs1(1,-1);
		trace1(1,-1);
	} else {
		for (int i = 1;i <= n;i++) res += gain[i];
		dfs3(1,-1);
	}
	
	cout << res << '\n' << sol.size() << '\n';
	for (auto x : sol) cout << x << " ";

}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5