Ticket Sales
National Olympiad — National round (2010 season)
Submission name: tickets.cpp
Problem summary
Cities form a weighted tree. City v has F[v] fans, each paying T if a ticket office lies within distance D. Opening an office costs S. Choose offices to maximize ticket revenue minus opening costs; leaving cities unserved, or opening no offices, is allowed.
Input
N T D S; then N fan counts; then N−1 lines a b length describing undirected roads. Cities are numbered from 1.
Output
The maximum profit.
Constraints
1 ≤ N,T ≤ 1000; 1 ≤ D ≤ 1000000; 1 ≤ S ≤ 1000000000; 0 ≤ F[v] ≤ 1000; 1 ≤ road length ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
7 10 5 100 5 11 0 0 13 10 1 1 3 3 2 3 3 4 3 2 4 7 4 1 5 5 4 6 6
Output
100
Solution analysis
- Root the tree at city 1. Let independent[v] be the best profit using offices and customers only in v’s subtree. Its first option leaves v unserved and sums the independent answers of its children. If v is served, choose an office c in its subtree with distance(v,c) ≤ D and pay S once for that office.
- An attached state (v,c) treats c as already paid for. If c belongs to v’s subtree, its path to v must stay attached: count the revenue at v, and process every child with the same c. In an off-path child, c is external. Such an external state either counts v’s revenue and continues with c, or discards external assistance and takes independent[v]. Once distance(v,c) exceeds D, all descendants are still farther from external c, so only the independent option remains.
- The external-state choice is sufficient because of nearest-office dominance. If another selected office z inside v’s subtree is no farther from v than c, then every descendant covered by c is also covered by z: distance(x,z) ≤ distance(x,v)+distance(v,z) ≤ distance(x,c). Thus external help can be discarded there. Otherwise c is the closest office at v and we count v’s revenue before descending. Memoization shares all (v,c) states; an Euler interval tests subtree membership in constant time.
- For the sample choose offices 4 and 5. Fans in cities 1,2,5,7 are served: 5+11+13+1 = 30 tickets give revenue 300, and two offices cost 200, yielding 100. The DP also allows the empty selection, ensuring the answer never becomes negative.
Why it works
Induct on subtree size. For an independent state, an unserved root allows independent child optima; a served root has a closest selected office c in its subtree. This office serves every vertex on its path to the root, so keeping that path attached is valid. In each branch away from that path, compare an external c with the closest selected internal office. When the internal one is closer at the branch root, the triangle inequality and the unique tree path show that it covers every descendant covered by c, so the independent optimum is sufficient. Otherwise c serves the branch root and the same argument applies recursively to its children. These alternatives represent an optimum. Every recurrence value corresponds to actual offices, pays each chosen office once, and counts every customer only in its own vertex state, establishing equality.
Watch out. Do not require every city to be served. Do not add the same customer’s revenue once per nearby office. A branch may use both external coverage near its root and new offices deeper down; replacing the whole branch immediately by one independent answer loses this option.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
using Profit=long long;
int main(){
int n,price,radius;
Profit cost;
cin>>n>>price>>radius>>cost;
vector<Profit>revenue(n);
for(Profit&value:revenue){
cin>>value;
value*=price;
}
vector<vector<pair<int,int>>>graph(n);
for(int i=1;i<n;i++){
int a,b,length;
cin>>a>>b>>length;
graph[--a].push_back({--b,length});
graph[b].push_back({a,length});
}
vector<vector<int>>distance(n,vector<int>(n));
for(int source=0;source<n;source++){
function<void(int,int)>visit=[&](int v,int parent){
for(auto[u,length]:graph[v]){
if(u!=parent){
distance[source][u]=distance[source][v]+length;
visit(u,v);
}
}
};
visit(source,-1);
}
vector<vector<int>>children(n);
vector<int>enter(n),leave(n);
int timer=0;
function<void(int,int)>root=[&](int v,int parent){
enter[v]=timer++;
for(auto[u,length]:graph[v]){
(void)length;
if(u!=parent){
children[v].push_back(u);
root(u,v);
}
}
leave[v]=timer;
};
root(0,-1);
auto contains=[&](int v,int c){
return enter[v]<=enter[c]&&enter[c]<leave[v];
};
vector<Profit>independent(n,-1);
vector<vector<Profit>>attached(n,vector<Profit>(n,-1));
function<Profit(int)>solve;
// The center c is already paid for. Its path to v is kept attached.
function<Profit(int,int)>attach=[&](int v,int c)->Profit{
Profit&answer=attached[v][c];
if(answer!=-1){
return answer;
}
if(distance[v][c]>radius){
return answer=solve(v);
}
answer=revenue[v];
for(int u:children[v]){
answer+=attach(u,c);
}
if(!contains(v,c)){
// A new center nearer v can replace the external center's help.
answer=max(answer,solve(v));
}
return answer;
};
solve=[&](int v)->Profit{
Profit&answer=independent[v];
if(answer!=-1){
return answer;
}
answer=0;
for(int u:children[v]){
answer+=solve(u);
}
for(int c=0;c<n;c++){
if(contains(v,c)&&distance[v][c]<=radius){
answer=max(answer,attach(v,c)-cost);
}
}
return answer;
};
cout<<solve(0)<<'\n';
}