我是题目链接

看了很多大佬的写法,一般都是树+深搜递归，但是个人总觉得如果是这样的话 5e5 来个恶心的树结构还是担心爆了（不过觉得用栈可能还是会比较好，在这里就只是谈一下我的一个比较 nc 的做法吧

首先，推出修剪次数=n/2，所以m=(n/2+1)/2。
下一步就是猜测了，设想一下，如果能保证通往最大叶子结点的路径都用大剪子，那么就一定可以取得最大值。于是乎，自然而然的想到最大值的上面都只能用大剪子不然根节点就无法取到最大值，而与最大叶子结点获得路径无关的地方其实是无所谓用什么剪子的。
那么就贪心一下呗，让每一把大剪子都为最大值服务=》m步以内从根出发能够达到的最大位置=》结点深度<m，可以使用大剪子。

至此，解题思路模拟完了，就是建树+求深度+（根据结点深度）遍历。

具体操作个人觉得根据代码理解比较好，就在代码里面以注释的方式给出啦（绝对不是因为懒~

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

struct node{
    int l,r,ran,s;
};
node t[1000009];//结点数组（储存树结构
node* tx[1000009];//根据结点深度对结点排序数组，其指向t数组，改变其顺序不改变t数组中顺序
int cmp(node* a,node* b){
    return a->s > b->s;//按从大到小排序，结点深度深的先求（因为根最浅而又是最后求
}
int main(){
    int n,m;
    cin>>n;
    m = (n/2+1)/2;//n与修剪次数是相关的
    int a,b,c;
    for(int i=0;i<=n;i++)
        t[i].s = 0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        t[i].l = a;
        t[i].r = b;
    }
    queue<int> qu;
    qu.push(1);
    while(!qu.empty()){//广搜求结点深度
        qu.push(0);
        while(qu.front()){
            c = qu.front();
            qu.pop();
            if(!t[c].l) continue;
            t[t[c].l].s = t[t[c].r].s = t[c].s+1;
            qu.push(t[c].l);    qu.push(t[c].r);
        }
        qu.pop();
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&(t[i].ran));
    for(int i=0;i<n;i++)//把tx与t一一对应
        tx[i] = &t[i+1];
    sort(tx,tx+n,cmp);//对tx进行排序，注意这里不会改变t中数组的结构（树结构不能变
    for(int i=0;i<n;i++){
        if(tx[i]->l == 0) continue;
        if(tx[i]->s >= m) //决定是否使用大剪子
            tx[i]->ran = min(t[tx[i]->l].ran,t[tx[i]->r].ran);
        else 
            tx[i]->ran = max(t[tx[i]->l].ran,t[tx[i]->r].ran);
    }
    cout<<t[1].ran;
    return 0;
}