题意

给一颗树，树边带权，有一些标记了的点，每个点可以在树上沿边移动，移动代价为边权。求一种移动策略，使得移动之后的树从根节点到每个叶子都至少有一个标记点，且每个点移动代价的最大值最小。最终状态下根节点不能带标记，无解输出-1

思路

1. 最值问题，且问题有单调性，可以二分，设当前要check的最大值为x，那么每个点都可以移动x

2. 对于一个带了标记的点来说，它的子树中的叶子都是满足条件的，如果把这个点向上移动，它能覆盖到的叶子只会多不会少，所以采用贪心策略，将每个点向上移动x，向上跳的过程可以用倍增完成，接下来分为两种情况（设跳到的点为i）：

   ①跳了x之后未到根。即i !=1，此时直接给i点打上标记，表示跳到这个点，这个是较简单的情况

   ②跳了x之后到了根。那么此时可以消耗的代价还有剩的，那么它可以从根节点走向其它的未标记点

3. 记录一下这个点到1的过程中经过的1的儿子节点（即depth==2的点），设它为j，对所有可以到1的标记点按照剩余代价从小到大排序，从小到大枚举，对于一个标记点，如果它的剩余代价小于dis(1,j)且j未被标记，那么就将它移动到j点，因为如果移动其它点的话会消耗dis(1,j)的代价，但是移动它只会消耗剩余代价，而剩余代价小于dis(1,j)，所以血赚不亏

4. 处理好j->1->j这种情况后，所有的点都当成是从1出发向某一个点，不考虑返回的情况，即使它就是从j->1->j。这就很简单了，对所有未标记的点到1的距离从大到小排序，对剩余代价大小从大到小排序，大的对应大的即可

P.S.标记可以从儿子向父亲转移，即如果一个点的所有儿子都带有标记，它也会带标记

Code：

#include
    
     #define N 50005typedef long long ll;const int temp=19;const ll INF = 10000000000000000;using namespace std;int n,m;int fa[N][temp],dep[N],r[N];ll dis[N][temp];vector< pair
     
       > rest;vector
      
        ret,q;bool v[N];//当前点的军队还可以走的路 struct Edge{    int next,to;    ll dis;}edge[N<<1];int head[N],cnt=1;void add_edge(int from,int to,ll dis){    edge[++cnt].next=head[from];    edge[cnt].to=to;    edge[cnt].dis=dis;    head[from]=cnt;}template 
       
        void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}void dfs(int rt){    dep[rt]=dep[fa[rt][0]]+1;    for(int i=head[rt];i;i=edge[i].next)    {        int to=edge[i].to;        if(to==fa[rt][0]) continue;        fa[to][0]=rt;        dis[to][0]=edge[i].dis;        for(int i=1;i
        
         b;}bool check(ll x)//每个军队可以走x {    rest.clear();    ret.clear();    q.clear();    memset(v,0,sizeof(v));    for(int i=1;i<=m;++i)    {        int now=r[i];//对now进行倍增，最多跳到dep==2         ll res=x;        for(int j=temp-1;j>=0;--j)        {            if(dep[fa[now][j]]>=2&&res>=dis[now][j])            {                res-=dis[now][j];                now=fa[now][j];            }        }        if(dep[now]!=2||res
         
          >1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<
          
           <