Политички Партии

#include <stdio.h>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

vector<int> bruteforce[50000];

struct Node
{
    Node* parent;
    vector<Node*> children;
    long long sum;
    long long power;
    bool deleted;

    void calculateSubtree()
    {
        sum=power;
        for(int i=0;i<children.size();++i)
        {
            children[i]->calculateSubtree();
            sum+=children[i]->sum;
        }
    }

    void addChild(Node* child)
    {
        children.push_back(child);
    }

    void setParent(Node* p)
    {
        parent=p;
    }

    void changeParentSum(long long n)
    {
        sum-=n;
        if(parent!=NULL)
            parent->changeParentSum(n);
    }

    void deleteIt()
    {
        for(int i=0;i<children.size();++i)
            children[i]->deleteIt();
        changeParentSum(sum);
        deleted=true;
    }

};

Node nodes[50000];
bool found[50000];

void reconstruct(int n)
{
    if(found[n])
        return;
    found[n]=true;
    for(int i=0;i<bruteforce[n].size();++i)
    {
        if(!found[bruteforce[n][i]])
        {
            nodes[n].addChild(&nodes[bruteforce[n][i]]);
            nodes[bruteforce[n][i]].setParent(&nodes[n]);
            reconstruct(bruteforce[n][i]);
        }
    }
}

int main()
{
    memset(found,false,sizeof(found));
    int n,k,a,b;
    scanf("%d%d",&n,&k);

    nodes[0].parent=NULL;

    for(int i=0;i<n;++i)
    {
        nodes[i].deleted=false;
        scanf("%I64d",&nodes[i].power);
    }

    found[0]=true;

    for(int i=0;i<n-1;++i)
    {
        scanf("%d%d",&a,&b);
        --a;
        --b;
        if(!found[a])
        {
            swap(a,b);
        }
        if(!found[a])
        {
            bruteforce[a].push_back(b);
            bruteforce[b].push_back(a);
        }
        else
        {
            nodes[a].addChild(&nodes[b]);
            nodes[b].setParent(&nodes[a]);
            reconstruct(b);
        }
    }

    nodes[0].calculateSubtree();

    while(k--)
    {
        int smallest=-1;
        for(int i=0;i<n;++i)
        {
            if(!nodes[i].deleted && (smallest==-1 || nodes[i].sum < nodes[smallest].sum))
                smallest=i;
        }

        if(nodes[smallest].sum>0)
            break;

        nodes[smallest].deleteIt();
    }

    printf("%I64d",nodes[0].sum);

    return 0;
}