咋没人写题解/fn
考虑行走的过程跟你 dfs 一棵树的过程是等价的，所以 \(T=0\) 时走的边数为 \(2(n-1)\)，\(T=1\) 时，当遍历完最后一个点 \(x\) 时，不用再回溯到 \(1\)，因此少了 \(dep_x\) 的时间。
那么你一旦进去一个点，你不走完它子树内的所有结点，它一定不会出来，倘若未走完就出来，则时间花费一定更劣。
考虑 \(T=0\) 时咋做，记 \(dp(x)\) 从 \(x\) 出发走完 \(x\) 子树并回到 \(x\) 的最小花费，显然你要安排各个儿子间的顺序，记其为序列 \(p\)，使得 \(\sum\limits_{i=1}dp(p_i)+sum(p_i)\sum\limits_{1\le j<i}2(sz_{p_j}+1)\) 最小，即一定是走第一个儿子，然后出来，此时第二个儿子的时间点就多了第一个走进去又走出来的时间。这种往往可以考虑单独拎两个考虑在 \(p\) 中的先后关系，你假设 \(x\) 先还是 \(y\) 先然后分别计算其贡献即可。又因为你这个偏序关系有传递性，所以你直接 sort 就是对的。需要注意的是，当你当前考虑的子树根不为 \(1\) 的时候，你应该设其初始时间为 \(1\)，这样你从父亲从儿子转移的时候才好转移，因为会经过一条边。而注意当考虑 \(1\) 的时候，初始时间应设为 \(0\)。这样设立的原因其实还有一点是你当根不为 \(1\) 时，你需要在根花费 1 单位时间。不这样的话，你可以不降 \(a_x\) 计入 \(dp_x\) 同样也可以做。
考虑 \(T=1\)，显然还是类似，只不过你一定存在一个点，使得它在它的祖先当中永远是最后走的。这个点需要满足其深度最深。当然，显然这个点不唯一。因此你要把这个点贪出来。具体的，在当前树根为 \(x\) 时，记当前有资格最后走的点集为 \(S\)，那么你不是最后走的你内部不必钦定最后走的点，只需按 \(T=0\) 的做法做即可。所以同样的，拎出 \((a,b)\) 进行比较即可。
总结，这类贪心确定排列顺序问题往往可以通过点对间的偏序来确定，因此分析的时候可以考虑一对，然后计算极端情况贡献，即仅考虑当前序列只有这两个元素，这两个元素的先后各自的贡献。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(2e5+5);
vector<int>g[N];
int n,T,t[N],sz[N],dp[N],a[N];
bool cmp(int x,int y) {
return (t[x]+2)*a[y]<(t[y]+2)*a[x];
}
void dfs(int x) {
sz[x]=1; dp[x]=a[x];
for(int y:g[x]) {
dfs(y); sz[x]+=sz[y]; a[x]+=a[y];
}
t[x]=2*(sz[x]-1);
sort(g[x].begin(),g[x].end(),cmp);
int res=1;
if(x==1) res=0;
for(int y:g[x]) {
dp[x]=dp[x]+res*a[y]+dp[y];
res+=t[y]+2;
}
}
int dep[N],mx[N],dp2[N];
void dfsmxd(int x) {
mx[x]=dep[x];
for(int y:g[x]) {
dep[y]=dep[x]+1;
dfsmxd(y);
mx[x]=max(mx[x],mx[y]);
}
}
int ed;
bool cmpp(int x,int y) {
return (t[x]+2)*a[y]+dp2[x]+dp[y]<(t[y]+2)*a[x]+dp2[y]+dp[x];
}
vector<int>vec1[N];
void dfs2(int x) {
sz[x]=1; dp[x]=dp2[x]=a[x];
for(int y:g[x]) {
dfs2(y); sz[x]+=sz[y]; a[x]+=a[y];
}
t[x]=2*(sz[x]-1);
for(int y:g[x]) {
if(mx[y]==mx[1]) vec1[x].pb(y);
}
sort(vec1[x].begin(),vec1[x].end(),cmpp);
ed=0;
if(!vec1[x].empty()) ed=vec1[x].back();
vector<int>vec; vec.clear();
for(int y:g[x]) if(y!=ed) vec.pb(y);
sort(vec.begin(),vec.end(),cmp);
int res=1;
if(x==1) res=0;
for(int y:vec) {
dp[x]=dp[x]+res*a[y]+dp2[y];
res+=t[y]+2;
}
if(ed) dp[x]=dp[x]+res*a[ed]+dp[ed];
res=1; if(x==1) res=0;
sort(g[x].begin(),g[x].end(),cmp);
for(int y:g[x]) {
dp2[x]+=res*a[y]+dp2[y];
res+=t[y]+2;
}
}
signed main() {
// freopen("11.in","r",stdin);
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>T;
for(int i=2;i<=n;i++) {
int x; cin>>x>>a[i];
g[x].pb(i);
}
if(T==0) {
dfs(1);
cout<<2*n-2<<" "<<dp[1];
} else {
dfsmxd(1);
cout<<2*n-2-mx[1]<<" ";
dfs2(1);
cout<<dp[1];
}
return 0;
}