Submission #67299

#	Time	Username	Problem	Language	Result	Execution time	Memory
67299		MANcity	Chase (CEOI17_chase)	C++14	0 / 100	17 ms	5744 KiB

chase

///GAGO_O
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n,k;
LL P[10002];
///sarqi LL
vector<vector<int> > g(100002);
LL dn[100002][102];
LL dv[100002][102];
LL sz[100002];
LL par[100002];
LL ANS[100002];
void dfs(int v,int p)
{
    par[v]=p;
    pair<LL,int> ma1[102];
    pair<LL,int> ma2[102];
    for0(i,k)
    {
        ma1[i].first=0;
        ma2[i].first=0;
        ma1[i].second=-1;
        ma2[i].second=-1;
    }
    for0(i,g[v].size()-1)
    {
        int to=g[v][i];
        if(to!=p)
        {
            dfs(to,v);
            for1(j,k)
            {
                dn[v][j]=max(dn[to][j],dn[to][j-1]+sz[v]-P[p]);
                if(dn[to][j]>ma1[j].first)
                {
                    ma2[j]=ma1[j];
                    ma1[j].first=dn[to][j];
                    ma1[j].second=i;
                }
                else
                if(dn[to][j]>ma2[j].first)
                {
                    ma2[j].first=dn[to][j];
                    ma2[j].second=i;
                }
            }
            for1(j,k)
            {
                LL t=0;
                if(j!=1)
                    t=P[to];
                dv[v][j]=max(dv[v][j],dv[to][j-1]+sz[v]-t);
            }
        }
    }
    ///hishi
    LL ma=0;
    for0(j,k)
    {
        ma=max(dv[v][j],ma);
        ma=max(dn[v][j],ma);
    }
    ANS[v]=max(ANS[v],ma);
    for0(j,k)
    for0(i,g[v].size()-1)
    {
        int to=g[v][i];
        if(to!=p)
        {
            LL S=dv[to][j];
            int q=ma1[k-j].second;
            if(q!=i && q!=-1)
            {
                ANS[v]=max(ANS[v],S+ma1[k-j].first);
            }
            q=ma2[k-j].second;
            if(q!=i && q!=-1)
            {
                ANS[v]=max(ANS[v],S+ma2[k-j].first);
            }
        }
    }
}
int main()
{
    cin>>n>>k;
    for1(i,n)
        cin>>P[i];
    for1(i,n-1)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for1(i,n)
    {
        for0(j,g[i].size()-1)
        {
            int to=g[i][j];
            sz[i]+=P[to];
        }
    }
    dfs(1,-1);
    LL ma=0;
    for1(i,n)
    {
        ma=max(ma,ANS[i]);
    }
    cout<<ma<<endl;
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30