Maximum Profit along a Tree Path
Autumn Tournament (2013)
Submission name: profit.cpp
Problem summary
A tree connects N cities. Each listed route is the unique path between two cities and carries positive profit. Choose one tree path and earn the profit of every listed route entirely contained in it. Print endpoints of a maximum-profit path and its profit.
Input
N, then N−1 tree edges. Next M, followed by M lines u v p describing routes and their profits.
Output
Print two chosen city numbers and their maximum total profit. Any optimum is accepted.
Constraints
2≤N≤100000; 0≤M≤100000; 1≤p≤1000.
Worked example
Official sample input with the same optimal path printed in reverse endpoint order. The source prints 5 1 31; either order is accepted.
Input
6 1 2 2 3 2 4 5 4 6 4 4 1 4 10 2 5 20 6 3 15 2 1 1
Output
1 5 31
Solution analysis
- Because rewards are nonnegative, extending a path cannot lower its profit. Therefore an optimum can be chosen with two distinct original tree leaves as endpoints. Root the tree, number its leaves in DFS order, and record the interval of leaf indices in each subtree. Also record ordinary vertex DFS entry times and subtree sizes for ancestor tests; leaf intervals alone cannot distinguish vertices on a chain.
- For a nontrivial route u–v, remove the first edge from u toward v and call the u-side leaf set A. Define B similarly at v. A chosen leaf-to-leaf path contains the route exactly when its endpoints lie one in A and one in B. If u is not an ancestor of v, A is u’s subtree interval. Otherwise find the child toward v with binary lifting; A is the complement of that child’s interval, represented by at most two intervals.
- Each pair of leaf intervals becomes a rectangle of endpoint pairs. Add profit p to A×B and B×A. At most one end of a nontrivial route needs a complemented interval, so at most four rectangles suffice. Convert each rectangle into a range-add event at its left X edge and a range-subtract event just after its right X edge.
- Sweep the first leaf endpoint in DFS order. A lazy segment tree over the second endpoint maintains accumulated profits and the best leaf index. Apply all events at the current first index, query the maximum excluding the same leaf, and retain the best endpoint pair. This transforms many overlapping tree routes into ordinary weighted rectangle coverage.
- The code also handles a route with equal endpoints u=v. Add its profit initially to every pair, then subtract it for pairs lying entirely in any one component of the tree after deleting u. Each child component is an interval; the parent-side component is a union of at most two intervals. Aggregate equal-endpoint profits per vertex, so these extra rectangles total O(N), not O(NM).
- In the sample, endpoints 5 and 1 lie on opposite far sides of routes 1–4,2–5 and2–1, giving 10+20+1. They do not contain route 6–3, so its 15 is not added. This is exactly the score obtained by the endpoint rectangles.
Why it works
Extending to leaves preserves every contained positive route. For distinct route endpoints, unique tree paths show containment is equivalent to selecting leaves in the two far-end components; the interval rectangles encode precisely those ordered pairs. For a one-vertex route, a path misses the vertex exactly when both endpoints lie in the same component after deleting it, justifying baseline subtraction. At every sweep position the segment tree therefore stores the exact profit for every second endpoint. Taking its maximum over all distinct leaf pairs returns a globally optimal path.
Complexity: O((N+M) log(N+M)) time and O(N log N + M) space. Binary lifting uses O(N log N); all ordinary routes create O(M) rectangles, and aggregated one-vertex routes create O(N) rectangles. Sorting events and logarithmic range updates dominate the sweep.
Watch out. Do not replace the far-end components by just the endpoint subtrees when one endpoint is an ancestor of the other. Original degree-one leaves include the root when it has degree one. Exclude equal leaf endpoints from queries. Keep vertex ancestor intervals separate from leaf intervals, and use long long for accumulated scores.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<utility>
#include<vector>
using namespace std;
struct Event{
int x,left,right;
long long value;
};
struct SegmentTree{
int n;
vector<long long>maximum,lazy;
vector<int>position;
explicit SegmentTree(int size):n(size),maximum(4*size),lazy(4*size),position(4*size){
build(1,0,n-1);
}
void build(int node,int left,int right){
position[node]=left;
if(left!=right){
int middle=(left+right)/2;
build(node*2,left,middle);
build(node*2+1,middle+1,right);
}
}
void apply(int node,long long value){
maximum[node]+=value;
lazy[node]+=value;
}
void push(int node){
apply(node*2,lazy[node]);
apply(node*2+1,lazy[node]);
lazy[node]=0;
}
void add(int node,int left,int right,int from,int to,long long value){
if(from<=left&&right<=to){
apply(node,value);
return;
}
push(node);
int middle=(left+right)/2;
if(from<=middle){
add(node*2,left,middle,from,to,value);
}
if(to>middle){
add(node*2+1,middle+1,right,from,to,value);
}
int best=maximum[node*2]>=maximum[node*2+1]?node*2:node*2+1;
maximum[node]=maximum[best];
position[node]=position[best];
}
pair<long long,int>query(int node,int left,int right,int from,int to){
if(from>to){
return {numeric_limits<long long>::lowest(),-1};
}
if(from<=left&&right<=to){
return {maximum[node],position[node]};
}
push(node);
int middle=(left+right)/2;
pair<long long,int>result{numeric_limits<long long>::lowest(),-1};
if(from<=middle){
result=max(result,query(node*2,left,middle,from,to));
}
if(to>middle){
result=max(result,query(node*2+1,middle+1,right,from,to));
}
return result;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>graph(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int levels=1;
while((1<<levels)<=n){
levels++;
}
vector<vector<int>>up(levels,vector<int>(n+1));
vector<int>depth(n+1),entry(n+1),subtree(n+1,1);
vector<int>leafLeft(n+1,n),leafRight(n+1,-1),leaves,order,stack{1};
while(!stack.empty()){
int v=stack.back();
stack.pop_back();
entry[v]=order.size();
order.push_back(v);
if(graph[v].size()==1){
leafLeft[v]=leafRight[v]=leaves.size();
leaves.push_back(v);
}
for(int to:graph[v]){
if(to!=up[0][v]){
up[0][to]=v;
depth[to]=depth[v]+1;
stack.push_back(to);
}
}
}
for(int i=n-1;i>0;i--){
int v=order[i],parent=up[0][v];
subtree[parent]+=subtree[v];
leafLeft[parent]=min(leafLeft[parent],leafLeft[v]);
leafRight[parent]=max(leafRight[parent],leafRight[v]);
}
for(int level=1;level<levels;level++){
for(int v=1;v<=n;v++){
up[level][v]=up[level-1][up[level-1][v]];
}
}
auto ancestor=[&](int u,int v){
return entry[u]<=entry[v]&&entry[v]<entry[u]+subtree[u];
};
int count=leaves.size();
auto complement=[&](int v){
vector<pair<int,int>>intervals;
if(leafLeft[v]>0){
intervals.push_back({0,leafLeft[v]-1});
}
if(leafRight[v]+1<count){
intervals.push_back({leafRight[v]+1,count-1});
}
return intervals;
};
auto farSide=[&](int u,int v){
if(!ancestor(u,v)){
return vector<pair<int,int>>{{leafLeft[u],leafRight[u]}};
}
int child=v,difference=depth[v]-depth[u]-1;
for(int level=0;level<levels;level++){
if((difference>>level)&1){
child=up[level][child];
}
}
return complement(child);
};
vector<Event>events;
auto rectangle=[&](pair<int,int>x,pair<int,int>y,long long value){
events.push_back({x.first,y.first,y.second,value});
events.push_back({x.second+1,y.first,y.second,-value});
};
int m;
cin>>m;
vector<long long>single(n+1);
long long baseline=0;
for(int i=0;i<m;i++){
int u,v,value;
cin>>u>>v>>value;
if(u==v){
single[u]+=value;
baseline+=value;
continue;
}
auto first=farSide(u,v);
auto second=farSide(v,u);
for(auto a:first){
for(auto b:second){
rectangle(a,b,value);
rectangle(b,a,value);
}
}
}
for(int v=1;v<=n;v++){
if(single[v]==0){
continue;
}
for(int to:graph[v]){
if(up[0][to]==v){
pair<int,int>interval{leafLeft[to],leafRight[to]};
rectangle(interval,interval,-single[v]);
}
}
if(v!=1){
auto outside=complement(v);
for(auto a:outside){
for(auto b:outside){
rectangle(a,b,-single[v]);
}
}
}
}
sort(events.begin(),events.end(),[](const Event&a,const Event&b){
return a.x<b.x;
});
SegmentTree tree(count);
tree.add(1,0,count-1,0,count-1,baseline);
size_t nextEvent=0;
long long best=-1;
int answerFirst=0,answerSecond=1;
for(int x=0;x<count;x++){
while(nextEvent<events.size()&&events[nextEvent].x==x){
const auto&event=events[nextEvent++];
tree.add(1,0,count-1,event.left,event.right,event.value);
}
// A nontrivial path has two distinct leaf endpoints.
auto candidate=
max(tree.query(1,0,count-1,0,x-1),tree.query(1,0,count-1,x+1,count-1));
if(candidate.first>best){
best=candidate.first;
answerFirst=x;
answerSecond=candidate.second;
}
}
cout<<leaves[answerFirst]<<' '<<leaves[answerSecond]<<' '<<best<<'\n';
}