记录编号	342287	评测结果	AAAAAAAAAA
题目名称	树的分割	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-11-08 11:21:03	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;

struct item {
    int sum;
    int num;
};

int n,k;
int w[30010];
vector<int> g[30010];

item dfs( int u , int fa , int minw ) {
    item rtn = {0,0};
    for( int i = 0 ; i < g[u].size() ; ++i ) {
        int v = g[u][i]; if( v == fa ) continue;
        item son = dfs(v,u,minw);
        rtn.num += son.num;
        rtn.sum += son.sum;
    }
    rtn.sum += w[u];
    if( rtn.sum >= minw ) { rtn.sum = 0; rtn.num++; }
    return rtn;
}

bool check( int minw ) {
    item it = dfs(1,-1,minw);
    if( it.num < k ) return false;
    else return true;
}

int main() {
    freopen( "tree.in" , "r" , stdin );
    freopen( "tree.out" , "w" , stdout );
    scanf( "%d%d" , &n , &k );
    int low = INF , high = 0;
    for( int i = 1 ; i <= n ; ++i ) {
        scanf( "%d" , &w[i] );
        low = min( low , w[i] );
        high += w[i];
    }
    for( int i = 0 ; i < n-1 ; ++i ) {
        int u,v; scanf( "%d%d" , &u , &v );
        g[u].push_back(v);
        g[v].push_back(u);
    }
    while( low < high ) {
        int mid = (low+high)/2+1;
        if( check(mid) ) low = mid;
        else high = mid-1;
    }
    printf( "%d\n" , low );
    return 0;
}