Proficient.
Put your skills to the test.

Problem summary

In a positively weighted tree, border towns are vertices of degree one. Choose a town minimizing the difference between its farthest and nearest border-town distance. If the chosen town is itself a border town, exclude itself. Break ties by the smallest town ID.

Constraints

2≤N≤1000000; edge lengths are positive integers at most 1000.

Worked example

An independently prepared example for this explanation.

6
6 2 2
6 1 3
6 4 2
6 3 6
1 5 7

1 4

Solution analysis

1. Root the tree at 1 with an iterative traversal. A reverse-order pass computes the minimum and maximum distance from each vertex to a border town in its subtree, including itself if its global degree is one.
2. In a forward pass, also know the minimum and maximum border distance through the parent. At each vertex, the candidate sources are its own zero-distance border status and one min/max contribution from each neighboring branch. Keep the best two minima and maxima with their source IDs, so a child’s own branch can be excluded in O(1) when passing information down.
3. Evaluate a town using neighboring branches only, which automatically excludes itself when it is a border town. For sample town 1, distances to border towns 2,4,3,5 are 5,5,9,7, giving difference 4. Scan IDs with a smallest-ID tie break.

Why it works

Removing an edge divides the tree into two components. The bottom-up states optimize border distances on the child side, and the top-down states combine every source on the other side, excluding exactly that child’s contribution. By induction all branch extrema are correct. Every other border town lies in exactly one neighboring branch, so their minimum and maximum produce the required difference for each candidate.

Watch out. Exclude a border town from its own evaluation but keep it as a distance source for other towns. Track source IDs when excluding a child, including ties. Use 64-bit distances.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
// Algorithm: Root the tree at 1 with an iterative traversal.
using namespace std;
struct Edge{
    int to;
    int weight;
    int next;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    vector<int>head(count+1,-1),degree(count+1,0);
    vector<Edge>edges;
    edges.reserve(2*(count-1));
    auto addEdge=[&](int from,int to,int weight){
        edges.push_back({to,weight,head[from]});
        head[from]=static_cast<int>(edges.size())-1;
        degree[from]++;
    };
    for(int i=1;i<count;i++){
        int a,b,weight;
        cin>>a>>b>>weight;
        addEdge(a,b,weight);
        addEdge(b,a,weight);
    }
    vector<int>parent(count+1,0),order;
    order.reserve(count);
    order.push_back(1);
    for(size_t index=0;index<order.size();index++){
        int vertex=order[index];
        for(int e=head[vertex];e!=-1;e=edges[e].next){
            int child=edges[e].to;
            if(child!=parent[vertex]){
                parent[child]=vertex;
                order.push_back(child);
            }
        }
    }
    const long long infinity=numeric_limits<long long>::max()/4;
    vector<long long>downMin(count+1,infinity),downMax(count+1,-infinity);
    vector<long long>upMin(count+1,infinity),upMax(count+1,-infinity);
    for(int index=count-1;index>=0;index--){
        int vertex=order[index];
        if(degree[vertex]==1){
            downMin[vertex]=0;
            downMax[vertex]=0;
        }
        for(int e=head[vertex];e!=-1;e=edges[e].next){
            int child=edges[e].to;
            if(parent[child]==vertex){
                downMin[vertex]=min(downMin[vertex],downMin[child]+edges[e].weight);
                downMax[vertex]=max(downMax[vertex],downMax[child]+edges[e].weight);
            }
        }
    }
    long long bestDifference=infinity;
    int bestTown=0;
    for(int vertex:order){
        long long min1=infinity;
        long long min2=infinity;
        long long max1=-infinity;
        long long max2=-infinity;
        int minSource=-2;
        int maxSource=-2;
        auto include=[&](long long low,long long high,int source){
            if(low<min1){
                min2=min1;
                min1=low;
                minSource=source;
            }
            else if(low<min2){
                min2=low;
            }
            if(high>max1){
                max2=max1;
                max1=high;
                maxSource=source;
            }
            else if(high>max2){
                max2=high;
            }
        };
        long long nearest=infinity;
        long long farthest=-infinity;
        for(int e=head[vertex];e!=-1;e=edges[e].next){
            int neighbor=edges[e].to;
            long long low=upMin[vertex];
            long long high=upMax[vertex];
            if(neighbor!=parent[vertex]){
                low=downMin[neighbor]+edges[e].weight;
                high=downMax[neighbor]+edges[e].weight;
            }
            nearest=min(nearest,low);
            farthest=max(farthest,high);
            include(low,high,neighbor);
        }
        long long difference=farthest-nearest;
        if(difference<bestDifference||(difference==bestDifference&&vertex<bestTown)){
            bestDifference=difference;
            bestTown=vertex;
        }
        if(degree[vertex]==1){
            include(0,0,-1);
        }
        for(int e=head[vertex];e!=-1;e=edges[e].next){
            int child=edges[e].to;
            if(parent[child]==vertex){
                upMin[child]=(minSource==child?min2:min1)+edges[e].weight;
                upMax[child]=(maxSource==child?max2:max1)+edges[e].weight;
            }
        }
    }
    cout<<bestTown<<' '<<bestDifference<<'\n';
}