C++14(g++5.4) 解法, 执行用时: 401ms, 内存消耗: 7268K, 提交时间: 2019-04-13 11:39:43

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,k;
ll mid;
vector<int> v[N];
ll dp[N];
int flag;
int val[N];
void dfs(int u,int fa)
{
	dp[u]=val[u];
	for(int i=0;i<v[u].size();i++)
	{
		int to=v[u][i];
		if(to==fa) continue;
		dfs(to,u);
		dp[u]+=dp[to];
	}
//	cout<<u<<" "<<dp[u]<<" "<<mid<<endl;
	if(dp[u]>=mid)
	{
		dp[u]=0;
		flag++;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	int x,y;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	ll l=1,r=1e10;
	ll ans=0;
	while(l<=r)
	{
		mid=(r+l)>>1;
		flag=0;
		dfs(1,0);
		
		if(flag>=k)
		{
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans<<endl;
	return 0;
 } 

C++11(clang++ 3.9) 解法, 执行用时: 246ms, 内存消耗: 7012K, 提交时间: 2019-04-13 12:02:29

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;

const int MAX_N=1e5+5;
int n,m,s;
LL w[MAX_N];
vector<int> e[MAX_N];

LL DFS(int u,int pre,LL Min);
int main()
{
	ios::sync_with_stdio(false); 
	cin>>n>>m;
	int u,v;
	for(int i=1;i<n;++i)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i)
		cin>>w[i];
	LL l=0,r=1e14,h;
	while(l<=r){
		h=(l+r)/2;	s=0;
		DFS(1,0,h);
		if(s>=m)	l=h+1;
		else	r=h-1;
	}
	cout<<r<<endl;
	
	return 0;
}

LL DFS(int u,int pre,LL Min)
{
	LL Sum=w[u];
	for(auto v:e[u])
		if(v!=pre){
			Sum+=DFS(v,u,Min);
		}
	if(Sum>=Min){
		++s;	Sum=0;
	}
	return Sum;
}