Water Levels along a Sewer Tree
Autumn Tournament (2007)
Submission name: porters.cpp
Problem summary
A rooted sewer tree receives 10 units of water per second at every vertex. A command may pump water from one vertex or ask for the minimum water level on an ancestor path, including both endpoints. Operations are ordered by time.
Source clarification. The sample pumps the root, although the pumping-command prose excludes it. Accepting root updates follows that sample and the natural tree model.
Input
N K; parents of vertices 2..N; then K commands k4i T X Y or cepy_lepy T X V.
Output
For each k4i command, print the maximum bale volume that can pass along the path.
Constraints
1≤N≤150000; 0≤T≤1000000; parent[v]<v. Y is an ancestor of X. A pump removes no more than the currently available water. The source does not separately bound K.
Worked example
Original statement sample.
Input
8 7 1 1 3 3 2 4 3 k4i 0 5 3 k4i 2 8 3 cepy_lepy 5 6 60 cepy_lepy 6 2 40 cepy_lepy 7 1 50 k4i 8 2 1 k4i 10 6 1
Output
0 20 30 40
Solution analysis
- At time T every vertex would contain 10T units without pumping. Let removed[v] be the cumulative amount pumped from v. Its actual level is 10T−removed[v], so a path minimum equals 10T minus the maximum removed value on that path. Rain therefore needs no range updates.
- Build heavy-light decomposition once. Each vertex receives a position in an array; a heavy chain is consecutive there. Store removed values in a maximum segment tree. A pump is one point addition. Split an ancestor path into heavy-chain intervals and query their maxima.
- In the sample, by time8 vertex2 has lost40 and vertex1 has lost50. Their levels are40 and30, so path2→1 allows volume30. At time10, path6→2→1 has removed values60,40,50; its minimum is100−60=40. Iterative preprocessing avoids recursion overflow on a long chain.
Why it works
All vertices share the same rainfall term 10T. Subtracting the largest cumulative removal gives exactly the smallest path level. Heavy-chain intervals partition the queried path without omissions or extra vertices, and the segment tree returns their combined maximum.
Watch out. Include both path endpoints. Pumping changes only the named vertex, not its subtree. The sample pumps vertex1 despite the pump prose saying X>1; this implementation accepts every vertex1..N. Use 64-bit water arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,commands;
cin>>n>>commands;
vector<int>parent(n+1),size(n+1,1),heavy(n+1,0);
vector<vector<int>>children(n+1);
for(int vertex=2;vertex<=n;vertex++){
cin>>parent[vertex];
children[parent[vertex]].push_back(vertex);
}
for(int vertex=n;vertex>=2;vertex--){
int p=parent[vertex];
size[p]+=size[vertex];
if(size[vertex]>size[heavy[p]]){
heavy[p]=vertex;
}
}
vector<int>head(n+1),position(n+1);
vector<pair<int,int>>pending{{1,1}};
int timer=0;
while(!pending.empty()){
auto[start,chain]=pending.back();
pending.pop_back();
for(int vertex=start;vertex!=0;vertex=heavy[vertex]){
head[vertex]=chain;
position[vertex]=timer++;
for(int child:children[vertex]){
if(child!=heavy[vertex]){
pending.push_back({child,child});
}
}
}
}
int base=1;
while(base<n){
base*=2;
}
vector<long long>tree(2*base,0);
auto maximum=[&](int left,int right){
long long answer=0;
for(left+=base,right+=base+1;left<right;left/=2,right/=2){
if(left%2){
answer=max(answer,tree[left++]);
}
if(right%2){
answer=max(answer,tree[--right]);
}
}
return answer;
};
while(commands--){
string kind;
long long time;
int x;
long long value;
cin>>kind>>time>>x>>value;
if(kind=="cepy_lepy"){
int index=base+position[x];
tree[index]+=value;
while(index>1){
index/=2;
tree[index]=max(tree[2*index],tree[2*index+1]);
}
}
else{
int ancestor=static_cast<int>(value);
long long removed=0;
// Only X moves upward because the other endpoint is its ancestor.
while(head[x]!=head[ancestor]){
removed=max(removed,maximum(position[head[x]],position[x]));
x=parent[head[x]];
}
removed=max(removed,maximum(position[ancestor],position[x]));
cout<<10*time-removed<<'\n';
}
}
}