题目链接
题目大意
有一颗有根树，每个边有边权。树的价值是根到所有叶子节点的边权和的总和即 .你可以进行一次操作使得任意一条边的边权值除以2，求最少进行多少次操作使得树的价值小于等于s
题目思路
一个常见的套路题吧，可惜自己没想出来，就是优先队列维护贪心即可
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,head[maxn],sz[maxn],cnt;
ll ans,sum,s;
priority_queue<struct node2> que;
struct node1{int to,next,w;
}e[maxn<<1];
struct node2{int w,sz;friend bool operator<(node2 a,node2 b){return 1ll*(a.w-(a.w/2))*a.sz<1ll*(b.w-(b.w/2))*b.sz;}
};
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt;
}
void init(){while(!que.empty()) que.pop();//一定注意要清空cnt=ans=sum=0;for(int i=1;i<=n;i++){sz[i]=head[i]=0;}
}
void dfs(int son,int fa){bool flag=1;//判断是否为根节点//sz[i]表示子代有几个叶子节点for(int i=head[son];i;i=e[i].next){if(e[i].to==fa) continue;flag=0;dfs(e[i].to,son);que.push({e[i].w,sz[e[i].to]});sum+=1ll*e[i].w*sz[e[i].to];sz[son]+=sz[e[i].to];}if(flag){sz[son]=1;}
}
signed main(){int _;scanf("%d",&_);while(_--){scanf("%d%lld",&n,&s);init();for(int i=1,u,v,w;i<=n-1;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w),add(v,u,w);}dfs(1,1);while(sum>s){ans++;int w=que.top().w,sz=que.top().sz;que.pop();sum-=1ll*(w-(w/2))*sz;que.push({w/2,sz});}printf("%lld\n",ans);}return 0;
}