本文共 1040 字，大约阅读时间需要 3 分钟。

二分

Description

给一颗树,有n个结点,编号为1到n，1为根节点,有两种操作，1 x y把x结点权值加y,2 x查询x到根节点所有结点的权值和.

Input

第一行输入一个整数t，代表有t组测试数据。

Output

对于每组查询输出一个整数表示结果

Sample Input

1

0

二分很实用，关键在怎样二分

#include
   
    #include
    
     using namespace std;int pa[50011],N,M;int ERFN(int x){    int ans=0,cot=0,i;    for(i=1;i<=N;i++)    {        if(x
     
      M-1)                return 1;        }    }    return 0;}int main(){    int T,low,high,a,mid,i;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&N,&M);        high=0;low=0;       for(i=1;i<=N;i++){            scanf("%d",&pa[i]);            high+=pa[i];            low=max(low,pa[i]);            }        while(low<=high){
  //建议 “<=” 二分标准写法            mid=(low+high)/2;            if(ERFN(mid))                low=mid+1;            else                high=mid-1;        }        printf("%d\n",low);    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/WYK1823376647/article/details/52234305 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！