Proficient.
Put your skills to the test.

Problem summary

A weighted tree is rooted at vertex 1. A pen starts there and must cover every edge without lifting. After reaching any vertex, additional friends may start their own continuous walks there. For each fee P per additional friend, minimize total distance walked plus P times the number of friends.

Constraints

1 ≤ T ≤ 5; 1 ≤ N,Q ≤ 10⁵; edge lengths and fees in [1,10⁹]; total Q across cases ≤10⁵.

Worked example

An independently prepared example for this explanation.

1
7
1 2 10
1 3 10
2 4 5
2 5 10
3 6 10
3 7 20
2
10
100

90
100

Solution analysis

1. Walking every edge down and back costs 2W, where W is the sum of edge lengths. Ending a pen’s route in a descendant avoids returning along one downward path. Decompose the tree’s edges into downward paths: at each vertex, continue the longest child path upward through its parent edge, and finish all other child paths there. Store every finished length and finally the root’s continuing length.
2. This produces a list of potential return-distance savings. The longest root path is available to the initial pen for free. Every other path can either be returned along, or be left unreturned by paying for one additional friend. A length s is worth selecting exactly when s>P, for a net saving s−P. Sort the remaining lengths and build suffix sums to answer each fee by binary search.
3. In the example the path lengths are 30,20,10,5 and W=65. The initial pen saves 30 for free, giving 100. For P=10, taking the extra path of length 20 saves another 10; taking the length-10 path ties. The answer is 90. At P=100 no extra path is worthwhile, giving 100.

Why it works

A useful strategy never needs more than one downward and one upward traversal of an edge. Relative to the full return walk, its savings can be represented by downward paths, with one free path from the root and one additional paid route for every other selected path. At a branch, suppose two continuing lengths satisfy a≥b and a parent segment of length e can extend one of them. Extending a produces lengths a+e,b instead of a,b+e. For every fee P, the sum of positive savings max(0,s−P) cannot decrease under this transfer to the longer path; the free root path also benefits from the longer continuation. Applying this exchange upward proves that always extending the maximum child path is optimal simultaneously for all fees. Choosing exactly the profitable resulting paid paths then gives the formula used by the code.

Watch out. Root at vertex 1. The initial pen pays no friend fee. A path with length exactly P can be ignored. Use 64-bit distances and iterative traversal for deep trees.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
// Algorithm: Walking every edge down and back costs 2W, where W is the sum of edge lengths.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        int n;
        cin>>n;
        vector<vector<pair<int,int>>>graph(n);
        long long weight=0;
        for(int i=1;i<n;++i){
            int u,v,length;
            cin>>u>>v>>length;
            --u;
            --v;
            graph[u].push_back({v,length});
            graph[v].push_back({u,length});
            weight+=length;
        }
        vector<int>parent(n,-1),order{0};
        for(size_t i=0;i<order.size();++i){
            int u=order[i];
            for(auto edge:graph[u]){
                if(edge.first!=parent[u]){
                    parent[edge.first]=u;
                    order.push_back(edge.first);
                }
            }
        }
        vector<long long>longest(n),savings;
        for(int index=n-1;index>=0;--index){
            int u=order[index];
            for(auto edge:graph[u]){
                if(parent[edge.first]==u){
                    long long path=longest[edge.first]+edge.second;
                    if(path>longest[u]){
                        swap(path,longest[u]);
                    }
                    if(path>0){
                        savings.push_back(path);
                    }
                }
            }
        }
        sort(savings.begin(),savings.end());
        vector<long long>prefix(savings.size()+1);
        for(size_t i=0;i<savings.size();++i){
            prefix[i+1]=prefix[i]+savings[i];
        }
        int q;
        cin>>q;
        while(q--){
            long long fee;
            cin>>fee;
            size_t first=upper_bound(savings.begin(),savings.end(),fee)-savings.begin();
            long long count=static_cast<long long>(savings.size()-first);
            long long extraSaving=prefix.back()-prefix[first]-count*fee;
            cout<<2*weight-longest[0]-extraSaving<<'\n';
        }
    }
}