题目链接

https://ac.nowcoder.com/acm/contest/8564/D

解题思路

可能很多人卡在思路上，实现不是很难。
大致思路：
找到只用大剪刀能剪到的所有叶子节点，再找到这些叶子节点的最大价值，就是答案。
严谨证明真不会，大致一说，我是这么想到的：
尽可能把所有叶子节点中价值最大的整上去，想得到这样的结果就得用足够的大剪刀，但存在某些情况不够用，那么我们肯定没法把最大的整上去；
整次大的？好像也不靠谱，万一次大的比最大的离根的距离还远咋办；
想让根尽可能大，我们就得用大剪刀剪，因为一旦用了小剪刀，在小剪刀之前用过的大剪刀就几乎是白用了，就好比你用了好几次大剪刀好不容易把100移到了某个位置，但是大剪刀用完了，只能用小剪刀，还是只能将100和另一个中较小者移上去，要是另一个比100小，做的无用功，用多次大剪刀后把小的移上去和直接把小的移上去的效果完全一样啊，还浪费了大剪刀；要是另一个比100大，那之前用的大剪刀更浪费，完全可以之前都用小剪刀，只在二者比较的时候使用大剪刀，把较大者移上去就好；
知道了用了小剪刀就会让原来的大剪刀失效，我们可以只用大剪刀去移动，也就有了我们的思路，找到只用大剪刀能剪到的所有叶子节点，再找到这些叶子节点的最大价值。

AC代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=5e5+100;

int vis[N],v[N],n,root,l,r,ans,m;
int mx[N];//mx[i]表示深度为i的叶子节点价值的最大值 
int dep[N];//表示节点i的深度 
vector<int> rt[N];//rt[i][0]存储节点i的左儿子的编号，rt[i][1]存储右儿子编号 


void dfs(int x,int d)//x表示节点编号，d表示深度 
{
    if(x==0) return ; 
    dep[x]=d;//节点x的深度为d 

    if(rt[x][0]==0) mx[d]=max(mx[d],v[x]);//如果x为叶子节点，刷新一下深度为d的叶子节点价值的最大值 
    dfs(rt[x][0],d+1);//访问左儿子 
    dfs(rt[x][1],d+1);//访问右儿子 
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        rt[i].pb(l);//根i的左儿子 
        rt[i].pb(r);//根i的右儿子 
        vis[l]=1;//当过儿子
        vis[r]=1;//当过儿子，肯定就不是整棵树的根了 
        if(l!=0 && r!=0) m++;//m含义如题 
    }    
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++)//找根 
    if(!vis[i])
    {
        root=i; 
        break;
    }

    dfs(root,1);

    m=++m/2;//此时m表示最多可使用大剪刀的次数 

    for(int i=1;i<=m+1;i++)//大剪刀可以使用m次，所以用大剪刀尽可能往深处剪可以剪到第m+1层 
    ans=max(mx[i],ans);//找到能用大剪刀剪到的最大价值 

    cout<<ans<<endl;
    return 0;
}