Submission #1327162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327162		simplemind_31	Travelling Trader (CCO23_day2problem2)	C++20	2 / 25	96 ms	30604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a,b,val[200000],sig1[200000];
vector<int> graph[200000];
ll dfs1(int node,int ante){
    ll maxi=0;
    for(auto u:graph[node]){
        if(u==ante)continue;
        ll temp=dfs1(u,node);
        if(temp>maxi){
            maxi=temp;
            sig1[node]=u;
        }
    }
    if(maxi==0)sig1[node]=node;
    return val[node]+maxi;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i=1;i<n;i++){
        cin >> a >> b;
        graph[--a].push_back(--b);
        graph[b].push_back(a);
    }
    for(int i=0;i<n;i++)cin >> val[i];
    if(k==1){
        cout << dfs1(0,-1) << '\n';
        vector<int> res;
        int now=0;
        while(now!=sig1[now]){
            res.push_back(now);
            now=sig1[now];
        }
        res.push_back(now);
        cout << res.size() << '\n';
        for(auto u:res)cout << u+1 << ' ';
        return 0;
    }
    if(k==2){
        
    }
}

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