贪心、动态规划、树形动态规划

赛时还以为是二分答案，结果没活了。

首先考虑指定树根，使用节点 $1$ 作根，考虑操作选择 $u$ 作为根，选择 $v$ 的子树会怎么样。如果 $1$ 为根节点时 $v$ 在 $u$ 的子树内部，操作就是在 $1$ 为根节点的情况下对 $v$ 进行子树加一。否则，令在以 $v$ 为根节点的情况下 $v$ 的包含 $u$ 的儿子为 $k$，相当于在 $1$ 为根节点的情况下对除了 $k$ 的子树外的所有点加一，等于全局加一后对 $k$ 进行子树减一操作。

现在和操作相关的点数从 $2$ 减少到 $1$，分别是：

• 对节点 $x$ 的子树加一。
• 全局加一，对节点 $x$ 的子树减一。

于是问题被简化了，考虑怎么做。全局加一不改变相对点权，只影响后续答案而不影响操作，可以放在后面考虑。

为了让答案最小，首先让所有叶子初始权值取到最小（子树加一可以无代价在任意时刻调整叶子权值，而子树减一会导致答案增加），即 $w_i = l_i$，然后考虑对非叶子节点根据儿子节点权值按照深度从大到小初始化，并使用最小次数的子树减一达到最终状态。

设计 $dp_i$ 为让 $i$ 子树中的权值全部等于 $i$ 的权值需要的最小全局加一次数。枚举 $i$ 的每个儿子 $j$，如果 $\max(w_j) \leq r_i$ 就直接初始化 $w_i = \max(\max(w_j),l_j)$ 后令 $dp_i = \sum dp_j$；否则初始化 $w_i = r_i$ 后令 $dp_i = \sum dp_j + \sum \max(w_j - r_i,0)$，最终答案为 $dp_1 + w_1$，总体时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
long long r[200'005],w[200'005],dp[200'005];
vector<int> v[200'005];
int n;
void dfs(int x,int las){
    for(int i:v[x]) if(i!=las){
        dfs(i,x);
        w[x]=max(w[x],w[i]);
        dp[x]+=dp[i];
    }
    w[x]=min(w[x],r[x]);
    for(int i:v[x]) if(i!=las) dp[x]+=max(w[i]-w[x],0ll);
}
void solution(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>r[i];
    for(int i=1;i<=n-1;i++){
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout<<w[1]+dp[1]<<'\n';
    for(int i=1;i<=n;i++) dp[i]=0,v[i].clear();
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}