📝 문제 정보#
문제 번역#
$N$개의 목초지가 있고 ($2 \le N \le 2\cdot 10^5$), $N-1$개의 도로로 연결되어 트리를 형성합니다. 모든 도로를 건너는 데 1초가 걸립니다. 각 목초지는 처음에 풀이 0개이고, $i$번째 목초지의 풀은 초당 $a_i$ ($1\le a_i\le 10^8$) 단위의 속도로 자랍니다. Farmer John은 처음에 목초지 1에 있으며, 모든 목초지의 풀에 비료를 주기 위해 돌아다녀야 합니다. 그가 $x$ 단위의 풀이 있는 목초지를 방문하면, $x$만큼의 비료가 필요합니다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않습니다.
입력에는 추가 매개변수 $T\in {0,1}$가 포함됩니다.
- $T=0$이면, Farmer John은 목초지 1에서 끝나야 합니다.
- $T=1$이면, Farmer John은 아무 목초지에서나 끝낼 수 있습니다.
모든 목초지에 비료를 주는 데 걸리는 최소 시간과 그 시간에 끝내는 데 필요한 최소 비료량을 계산하세요.
입력#
첫 번째 줄에 $N$과 $T$가 주어집니다.
그 다음 $i$가 $2$부터 $N$까지 각각에 대해, $p_i$와 $a_i$를 포함하는 줄이 주어집니다. 이는 목초지 $p_i$와 $i$를 연결하는 도로가 있다는 의미입니다. $1\le p_i 최소 시간과 최소 비료량을 공백으로 구분하여 출력합니다.출력#
🧐 관찰 및 접근#
💻 풀이#
struct Node{
// Type 0
ll time; // 해당 서브트리를 다 처리하는데 걸리는 시간
ll a_sum; // 해당 서브트리의 a_i의 합
ll cost; // 해당 서브트리를 다 처리하는데 드는 비용 (0초 시작 가정)
// Type 1
ll mxDepth; // 해당 서브트리 내 최대 깊이
ll cost2; // 해당 서브트리를 다 처리하는데 드는 비용, 해당 서브트리 안의 가장 깊은 노드에서 끝남
Node(ll time = 0, ll a_sum = 0, ll cost = 0, ll mxDepth = 0, ll cost2 = 0) : time(time), a_sum(a_sum), cost(cost), mxDepth(mxDepth), cost2(cost2) {}
};
vector<int> links[200010];
int a[200010];
Node nodes[200010];
Node dfs(int c){
if(links[c].empty()){
nodes[c] = Node(0, a[c], 0, 0, 0);
return nodes[c];
}
vector<Node> children;
for(auto nxt: links[c]) children.push_back(dfs(nxt));
sort(all(children), [](Node &x, Node &y){
return x.a_sum * (y.time+2) > y.a_sum * (x.time+2);
});
auto &cur = nodes[c];
cur.a_sum = a[c];
for(auto &child: children){
cur.cost += child.cost + child.a_sum * (cur.time + 1);
cur.time += child.time + 2;
cur.a_sum += child.a_sum;
cur.mxDepth = max(cur.mxDepth, child.mxDepth + 1);
}
// cost2: 최대깊이 자식을 맨 뒤로 보내면서 계산해보기
int sz = children.size();
vector<ll> discover_time(sz, 0), sufSm(sz+1, 0);
ll totTime = 0;
rep(i, 0, sz){
discover_time[i] = totTime + 1;
totTime += children[i].time + 2;
}
rrep(i, 0, sz) sufSm[i] = sufSm[i+1] + children[i].a_sum;
cur.cost2 = 2e18;
rep(i, 0, sz){
auto &child = children[i];
if(child.mxDepth != cur.mxDepth - 1) continue;
ll tmp = cur.cost;
ll child_time = child.time + 2;
tmp -= child_time * sufSm[i+1]; // 뒤에있는 자식들 땡겨오기
tmp += child.a_sum * ((cur.time - discover_time[i] + 1) - child_time); // child를 뒤로 보냈으니 그만큼 드는 추가시간
tmp -= child.cost;
tmp += child.cost2; // child는 최대깊이 자식이므로 cost2로 계산
cur.cost2 = min(cur.cost2, tmp);
}
return cur;
}
void solve(){
int N, T; cin >> N >> T;
rep(i, 2, N+1){
int p; cin >> p;
links[p].push_back(i);
cin >> a[i];
}
dfs(1);
if(T == 0) cout << nodes[1].time << ' ' << nodes[1].cost;
else cout << nodes[1].time - nodes[1].mxDepth << ' ' << nodes[1].cost2;
}