题解 | 种树

我们主要考虑什么时候用大剪刀，可以使用大剪刀的次数为（m+1）/2，为了使根的值最大，我们一定要在1处使用大剪刀，为了使一的两个左右节点大，我们也要选择使用大剪刀，由此可推出我们要在靠近1的分叉去使用大剪刀，这里设1的深度为1，举个例子，我们能使用大剪刀的次数为2，那我们要在深度小于2的时候使用大剪刀，以下给出解释：

假设1的左右子树都不是叶子节点，我们使用大剪刀的次数只有两次，那到底是给1的左子树还是右子树呢，我们可以对其全用大剪刀，因为1的最大值一定从左右子树中出现，而且只是其中一个值，因为，我们对1的左右子树全用大剪刀的结果跟只对1的左子树用大剪刀或只对1的右子树用大剪刀结果是一样的，所有这时我们只需要考虑深度就行了 ，深度小于m的就用大剪刀。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

void solve(){
    int n;cin>>n;
    int m=0;
    vector<pair<int,int>> e(n+1);
    vector<int> val(n+1);
    for(int i=1;i<=n;i++){
        cin>>e[i].first>>e[i].second;
        if(e[i].first!=0) m++;
    }
    for(int i=1;i<=n;i++) cin>>val[i];
    m=(m+1)/2;
    auto dfs=[&](auto dfs,int u,int d)->void{
        if(e[u].first==0) return;
        dfs(dfs,e[u].first,d+1);
        dfs(dfs,e[u].second,d+1);
        if(d<=m) val[u]=max(val[e[u].first],val[e[u].second]);
        else val[u]=min(val[e[u].first],val[e[u].second]);
    };
    dfs(dfs,1,1);
    cout<<val[1];
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}